#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long int
#define cerr if(0) cerr
const int N = 5000;
ll dp[N][N][2], A[N], B[N], C[N]; // 0 - 1
vector<pair<int, ll>> g[N];
bitset<N> in_path;
int sz[N];
bool dfs(int v, int p, int t, vector<int> &T){
T.pb(v);
if(v == t){
return 1;
}
for(auto [u, w]: g[v]){
if(u != p){
bool ok = dfs(u, v, t, T);
if(ok) return true;
}
}
T.pop_back();
return false;
}
void dfs2(int v, int p){
vi U;
sz[v] = 1;
for(auto [u, w]: g[v]){
if(u != p && !in_path[u]){
dfs2(u, v);
sz[v] += sz[u];
U.pb(u);
}
}
for(int j = 0; j <= sz[v]; ++j) dp[v][j][0] = 1e18;
dp[v][0][0] = 0;
int cur = 0;
for(int u: U){
cur += sz[u];
for(int w = cur; w >= 1; --w){
for(int j = 1; j <= sz[u]; ++j){
if(w - j < 0) break;
dp[v][w][0] = min(dp[v][w][0], dp[v][w - j][0] + dp[u][j][0]);
}
}
}
for(int j = sz[v]; j >= 1; --j) dp[v][j][0] = dp[v][j - 1][0] + A[v];
for(int j = 0; j <= sz[v] * 2; ++j) dp[v][j][1] = 1e18;
dp[v][0][1] = 0;
cur = 0;
for(int u: U){
cur += sz[u]*2;
for(int w = cur*2; w >= 1; --w){
for(int j = 1; j <= sz[u]*2; ++j){
if(w - j < 0) break;
dp[v][w][1] = min(dp[v][w][1], dp[v][w - j][1] + dp[u][j][1]);
}
for(int j = 1; j <= sz[u]; ++j){
if(w - j < 0) break;
dp[v][w][1] = min(dp[v][w][1], dp[v][w - j][1] + dp[u][j][0]);
}
}
}
for(int j = sz[v] * 2; j >= 2; --j) dp[v][j][1] = dp[v][j - 2][1] + B[v] + A[v];
dp[v][1][1] = 1e18; // impossible case lol
}
int max_score(int n, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
for(int i = 0; i < n; ++i) g[i].clear();
in_path = 0;
for(int i = 0; i < n-1; ++i){
g[U[i]].pb({V[i], W[i]});
g[V[i]].pb({U[i], W[i]});
}
vector<ll> dist(n, -1);
dist[X] = 0;
queue<int> q;
q.push(X);
while(!q.empty()){
int v = q.front(); q.pop();
for(auto [u, w]: g[v]){
if(dist[u] == -1){
dist[u] = dist[v] + w;
q.push(u);
}
}
}
vector<ll> dist2(n, -1);
dist2[Y] = 0;
q.push(Y);
while(!q.empty()){
int v = q.front(); q.pop();
for(auto [u, w]: g[v]){
if(dist2[u] == -1){
dist2[u] = dist2[v] + w;
q.push(u);
}
}
}
for(int i = 0; i < n; ++i){
A[i] = min(dist[i], dist2[i]);
B[i] = max(dist[i], dist2[i]) - min(dist[i], dist2[i]);
}
vi T;
dfs(X, X, Y, T);
for(int x: T) in_path[x] = 1;
ll sum = 0;
for(int x: T){
sum += A[x];
}
int ans = 0;
ll KK = K;
for(int j = 0; j < n; ++j) C[j] = A[j];
sort(C, C+n);
for(int j = 0; j < n; ++j){
if(KK>= C[j]) KK-=C[j], ++ans;
}
for(int x: T){
K -= A[x];
A[x] = 0;
}
vector<ll> DP(2*n + 5, 1ll*(1e18));
cerr << ans << " f\n";
for(int i = 0; i < n; ++i){
cerr << A[i] << ' ' << B[i] << '\n';
}
cerr << '\n';
DP[0] = 0;
int cur = 0;
for(int v: T){
dfs2(v, v);
cur += sz[v] * 2;
for(int j = cur; j >= 0; --j){
for(int w = 1; w <= 2*sz[v]; ++w){
if(j - w < 0) break;
if(w <= sz[v]){
DP[j] = min(DP[j], DP[j - w] + dp[v][w][0]);
}
DP[j] = min(DP[j], DP[j - w] + dp[v][w][1]);
}
}
for(int j = 0; j <= cur; ++j){
cerr << DP[j] << ' ';
}
cerr << '\n';
}
cerr << '\n';
cerr << '\n';
for(int v = 0; v < n; ++v){
cerr << v << ' ' << sz[v] << ":\n";
for(int j = 0; j <= sz[v]; ++j){
cerr << dp[v][j][0] << ' ';
}
cerr << '\n';
}
for(int i = 2*n; i >= 0; --i) if(DP[i] <= K) return max(i, ans);
return ans;
}
