#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;
if(x > y) {
swap(x, y);
for(int i=1; i<=n; i++) swap(a[i], b[i]);
}
for(int i=x; i<=n; i++) {
for(int j=y; j>=1; j--) {
ll tmp = k;
int res = 0;
vector<ll> vec;
if(i < j) {
for(int f=x; f<=i; f++) {
vec.pb(a[f]);
}
for(int f=j; f<=y; f++) {
vec.pb(b[f]);
}
} else {
for(int f=j; f<=i; f++) {
tmp -= max(a[f], b[f]);
}
for(int f=x; f<j; f++) {
tmp -= a[f];
}
for(int f = i+1; f<=y; f++) {
tmp -= b[f];
}
res = (i - x + 1) + (y - j + 1);
}
if(tmp < 0) continue;
for(int f=min(x-1, (ll)j-1); f>=1; f--) vec.pb(a[f]);
for(int f=max(y+1, (ll)i+1); f<=n; f++) vec.pb(b[f]);
sort(all(vec));
reverse(all(vec));
while(size(vec) > 0 && tmp >= vec.back()) {
tmp -=vec.back();
vec.pop_back();
res ++;
}
ans = max(ans, res);
}
}
for(int i=0; i<=n; i++) adj[i].clear(), mark[i] = 0;
return ans;
}
