#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const long long N = 3010;
long long dp[N][2*N];
vector <pair <long long, long long>> g[N];
long long mark[N];
long long custox[N], custoy[N];
long long l[N], r[N];
int pai[N];
int esp[N];
void dfs_x(int v, int p){
pai[v] = p;
for(auto [x, w] : g[v]){
if(x == p)
continue;
custox[x] = custox[v] + w;
dfs_x(x, v);
}
return;
}
void dfs_y(int v, int p){
for(auto [x, w] : g[v]){
if(x == p)
continue;
custoy[x] = custoy[v] + w;
dfs_y(x, v);
}
return;
}
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();
mark[i] = 0;
custox[i] = custoy[i] = 0;
for(int j = 0;j < 2*n+2;j++)
dp[i][j] = 0;
l[i] = r[i] = 0;
pai[i] = 0;
esp[i] = 0;
}
for(long long i = 0;i < n-1;i++){
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
priority_queue <pair <long long, long long>> pq;
pq.push({0, X});
pq.push({0, Y});
long long ans = 0, sum = 0;
while(!pq.empty()){
auto [w, v] = pq.top();
pq.pop();
if(mark[v])
continue;
w *= -1;
if(sum+w > k){
break;
}
sum += w;
ans++;
mark[v] = 1;
for(auto [x, ww] : g[v]){
if(mark[x])
continue;
pq.push({-(ww+w), x});
}
}
dfs_x(X, X);
dfs_y(Y, Y);
for(int i = 0;i < n;i++){
l[i] = min(custox[i], custoy[i]);
r[i] = max(custox[i], custoy[i]) - l[i];
}
long long calc = 0;
int pref = 0;
while(Y != X){
esp[Y] = 1;
calc += l[Y];
Y = pai[Y];
pref++;
}
esp[X] = 1;
pref++;
if(calc > k)
return ans;
//cout << pref << ' ' << calc << '\n';
k -= calc;
for(int i = 0;i < n;i++){
for(int j = 0;j < 2*n+2;j++){
dp[i][j] = 1e18+10;
}
}
dp[0][0] = 0;
if(esp[0] == 0){
dp[0][1] = l[0];
dp[0][2] = l[0] + r[0];
}
else{
dp[0][1] = r[0];
}
for(int i = 1;i < n;i++){
for(int j = 0;j < 2*n+2;j++){
if(esp[i] == 0){
dp[i][j] = min(min(dp[i][j], dp[i-1][j]), min((j > 0 ? dp[i-1][j-1] + l[i] : (long long)(1e18+10)), (j > 1 ? dp[i-1][j-2] + l[i] + r[i] : (long long)(1e18+10))));
}
else{
dp[i][j] = min({dp[i][j], dp[i-1][j], (j > 0 ? dp[i-1][j-1] + r[i] : (long long)(1e18+10))});
}
}
}
for(int i = 0;i < 2*n+2;i++){
//cout << dp[n-1][i] << ' ';
}
for(int i = 2*n+1;i >= 0;i--){
if(dp[n-1][i] <= k){
return max((long long)(i+pref), ans);
}
}
}
