//#include "closing.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define pb push_back
using namespace std;
using ll = long long int;
using vi = vector<int>;
template<typename T>
using vec = vector<T>;
template<typename T>
using pq_min = priority_queue<T,vector<T>,greater<T>>;
using pii = pair<int, int>;
using iii = array<ll,3>;
const int N=6005;
const ll inf=2e18;
ll dp[N][N][4], dis[3][N];
vec<pii> adj[N];
int tin[N], tout[N], timer, sz[N];
void dfs(int u, int p){
tin[u]=timer++;
repa(v,adj[u]) if(v.fi!=p) dfs(v.fi,u);
tout[u]=timer++;
}
void solve(int u, int p, int x, int y){
dp[u][0][0]=0;
dp[u][1][2]=dis[0][u];
dp[u][1][1]=dis[1][u];
dp[u][2][3]=dis[2][u];
sz[u]=1;
repa(e,adj[u]){
int v=e.fi;
if(v==p) continue;
solve(v,u,x,y);
rep(j,0,2*sz[v]+1){
repr(i,2*sz[u]+1,0){
rep(mask,0,4){
rep(mask2,0,4){
if((mask2&2) && !(mask&2) && !(tin[v]<tin[x] && tout[x]<tout[v])) continue;
if((mask2&1) && !(mask&1) && !(tin[v]<tin[y] && tout[y]<tout[v])) continue;
if((mask&2) && !(mask2&2) && (tin[v]<=tin[x] && tout[x]<=tout[v])) continue;
if((mask&1) && !(mask2&1) && (tin[v]<=tin[y] && tout[y]<=tout[v])) continue;
dp[u][i+j][mask]=min(dp[u][i+j][mask],dp[u][i][mask]+dp[v][j][mask2]);
}
}
}
}
sz[u]+=sz[v];
}
}
int max_score(int n, int x, int y, ll k, vi u, vi v, vi w){
if(n>3000) return 0;
rep(i,0,n) adj[i].clear();
rep(i,0,n-1){
adj[u[i]].pb({v[i],w[i]});
adj[v[i]].pb({u[i],w[i]});
}
pq_min<iii> pq;
pq.push({0,x,0});
pq.push({0,y,1});
int a, b, d;
rep(i,0,n) dis[0][i]=dis[1][i]=inf;
dis[0][x]=0;
dis[1][y]=0;
while(pq.size()){
a=pq.top()[1];
b=pq.top()[2];
d=pq.top()[0];
pq.pop();
if(d>dis[b][a]) continue;
repa(c,adj[a]){
if(c.se+dis[b][a]>=dis[b][c.fi]) continue;
dis[b][c.fi]=c.se+dis[b][a];
pq.push({dis[b][c.fi],c.fi,b});
}
}
rep(i,0,n) dis[2][i]=max(dis[0][i],dis[1][i]);
rep(i,0,n) rep(j,0,2*n+1) rep(mask,0,4) dp[i][j][mask]=inf;
timer=0;
dfs(0,-1);
solve(0,-1,x,y);
repr(i,n*2+1,0) rep(mask,0,4) if(dp[0][i][mask]<=k) return i;
return 0;
}
