#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
ll MOD(ll a, ll mod=Mod) {
a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
ll res = 1;
while(b > 0) {
if(b%2 == 1) res = MOD(res * a, mod);
b /= 2;
a = MOD(a * a, mod);
}
return res;
}
ll t, n, x, y, k, dp[3003][3003][3], pd[3003][3], a[N], b[N], subt[N];
vector<pll> adj[N];
void dfs(int v, int p=0, ll sum = 0) {
a[v] = sum;
for(auto u : adj[v]) {
if(u.F == p) continue;
dfs(u.F, v, u.S + sum);
}
}
void dfs2(int v, int p=0, ll sum = 0) {
b[v] = sum;
for(auto u : adj[v]) {
if(u.F == p) continue;
dfs2(u.F, v, u.S + sum);
}
}
void calc(int v, int p=0) {
for(int i=1; i<=n*2; i++) {
dp[v][i][0] = 1e18 + 1;
dp[v][i][1] = 1e18 + 1;
dp[v][i][2] = 1e18 + 1;
}
dp[v][0][1] = 1e18 + 1;
dp[v][0][2] = 0;
dp[v][1][0] = dp[v][1][2] = a[v];
dp[v][2][1] = b[v];
subt[v] = 1;
if(size(adj[v]) == 1 && p > 0) {
return;
}
for(auto u : adj[v]) {
if(u.F == p) continue;
calc(u.F, v);
for(int i=0; i<=(subt[v] + subt[u.F])*2; i++) {
pd[i][0] = pd[i][1] = pd[i][2] = 1e18 + 1;
}
for(int i=0; i<=subt[v]*2; i++) {
for(int j=0; j<=subt[u.F]*2; j++) {
pd[i + j][0] = min(dp[v][i][0] + dp[u.F][j][0], pd[i + j][0]);
pd[i + j][1] = min(dp[v][i][1] + min(dp[u.F][j][0], dp[u.F][j][1]), pd[i + j][1]);
pd[i + j][2] = min({dp[v][i][2] + dp[u.F][j][0],
dp[v][i][0] + min(dp[u.F][j][2], dp[u.F][j][1]), pd[i+j][2]});
}
}
subt[v] += subt[u.F];
for(int i=0; i<=subt[v]*2; i++) {
dp[v][i][0] = pd[i][0];
dp[v][i][1] = pd[i][1];
dp[v][i][2] = pd[i][2];
}
}
}
int mark[N];
int max_score(int _N, int _X, int _Y, long long _K, vector<int> U, vector<int> V, vector<int> W) {
n = _N, k = _K, x = _X, y = _Y;
x ++, y ++;
for(int i=0; i<n-1; i++) {
adj[V[i] + 1].pb({U[i] + 1, W[i]});
adj[U[i] + 1].pb({V[i] + 1, W[i]});
}
dfs(x);
dfs2(y);
int ans = 0;
priority_queue<pll, vector<pll>, greater<pll>> pq;
pq.push({0, x});
pq.push({0, y});
while(size(pq) > 0) {
pll v = pq.top(); pq.pop();
if(mark[v.S] == 1) continue;
if(v.F > k) continue;
k -= v.F;
ans ++;
mark[v.S] = 1;
for(auto it : adj[v.S]) {
if(mark[it.F] == 0) {
pq.push({min(a[it.F], b[it.F]), it.F});
}
}
}
// for(int i=1; i<=n; i++) {
// if(a[i] > b[i]) swap(a[i], b[i]);
// }
// calc(x);
// int mx = 0;
// for(int i=x; i<=x; i++) {
// for(int j=1; j<=subt[i]*2; j++) {
// if(dp[i][j][2] <= k) mx = max(mx, j);
// if(dp[i][j][1] <= k) mx = max(mx, j);
// if(dp[i][j][0] <= k) mx = max(mx, j);
// }
// }
for(int i=0; i<=n; i++) adj[i].clear(), mark[i] = 0;
return ans;
}
