//#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=3005, N2=2e5;
const ll inf=2e18;
ll dp[N][N*2][4], dp2[N][N*2][4], dis[3][N];
vec<pii> adj[N2];
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){
sz[u]=1;
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];
repa(e,adj[u]){
int v=e.fi;
if(v==p) continue;
solve(v,u,x,y);
vec<pii> vt;
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;
vt.pb({mask,mask2});
}
}
rep(j,0,2*sz[v]+1){
repr(i,2*sz[u]+1,0){
rep(k,0,(int)vt.size()){
dp2[u][i+j][vt[k].fi]=min(dp2[u][i+j][vt[k].fi],dp[u][i][vt[k].fi]+dp[v][j][vt[k].se]);
}
}
}
sz[u]+=sz[v];
rep(j,0,2*sz[u]+1) rep(mask,0,4) dp[u][j][mask]=dp2[u][j][mask], dp2[u][j][mask]=inf;
}
}
int max_score(int n, int x, int y, ll k, vi u, vi v, vi w){
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;
ll ans=0, sum=k;
while(pq.size()){
a=pq.top()[1];
b=pq.top()[2];
d=pq.top()[0];
pq.pop();
if(d>dis[b][a]) continue;
sum-=d;
if(sum>=0) ans++;
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});
}
}
if(dis[0][y]>2*k) return ans;
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]=dp2[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;
}
