#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[200005];
ll disa[200005];
ll disb[200005];
int vis[200005];
ll cos1[200005];
ll cos2[200005];
ll ne[200005];
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;
return max(tot1, tot2);
}
