#include <iostream>
#include <vector>
#include "closing.h"
#include <algorithm>
using namespace std;
#define ll long long
struct edg{
int no;
ll len;
};
int tot1;
int tot2;
vector<edg> adj[5000];
ll disa[5000];
ll disb[5000];
int vis[5000];
ll dp[3005][6005];
ll cos1[5000];
ll cos2[5000];
ll ne[5000];
ll sm;
void dfs1(int nod, ll di){
vis[nod] = 1;
disa[nod] = di;
for(auto edge : adj[nod]){
int n1 = edge.no;
int n2 = edge.len;
if(vis[n1]==0){
dfs1(n1, di+n2);
}
}
}
void dfs2(int nod, ll di){
vis[nod] = 1;
disb[nod] = di;
for(auto edge : adj[nod]){
int n1 = edge.no;
int n2 = edge.len;
if(vis[n1]==0){
dfs2(n1, di+n2);
}
}
}
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w){
for(int i=0; i<n; i++){adj[i].clear();}
for(int i=0; i<n-1; i++){
adj[u[i]].emplace_back(edg{v[i],1LL * w[i]});
adj[v[i]].emplace_back(edg{u[i],1LL * w[i]});
}
for(int i=0; i<n; i++){
vis[i]=0;
disa[i]=0LL;
disb[i]=0LL;
}
dfs1(x, 0LL);
for(int i=0; i<n; i++){
vis[i]=0;
}
dfs2(y,0LL);
for(int i=0; i<n; i++){
cos1[i] = min(disa[i], disb[i]);
cos2[i] = max(disa[i], disb[i]);
}
for(int i=0; i<n; i++){
ne[i] = cos1[i];
}
sort(ne, ne+n);
tot1=0;
sm=0LL;
for(int i=0; i<n; i++){
if(sm+ne[i]<=k){
sm += ne[i]; tot1++;
}
}
tot2=0;
for(int i=0; i<=n; i++){
for(int j=0; j<=2*n; j++){
dp[i][j] = k+1;
}
}
dp[0][0]=0;
for(int i=0; i<n; i++){
for(int j=0; j<=2*i; j++){
dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + cos1[i]);
dp[i+1][j+2] = min(dp[i+1][j+2], dp[i][j] + cos2[i]);
if(disa[i]+disb[i]>disa[y]){
dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
}
}
}
for(int i=1; i<=2*n; i++){
if(dp[n][i]<=k){
tot2 = i;
}
}
return max(tot1, tot2);
}
