#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")
const int mxN = 1e6 + 5;
ll n,dis[mxN];
vector<pair<ll,ll>> v[mxN];
void dfs(ll at, ll par){
for(auto it : v[at]){
if(it.ff == par) continue;
dis[it.ff] = dis[at] + it.sd;
dfs(it.ff, at);
}
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W){
n = N;
for(int i = 0; i < n - 1; i++){
v[U[i]].pb({V[i], W[i]});
v[V[i]].pb({U[i], W[i]});
}
dis[X] = 0;
dfs(X, X);
multiset<ll> s;
for(int i = 0; i < n; i++) s.insert(dis[i]);
dis[Y] = 0;
dfs(Y, Y);
for(int i = 0; i < n; i++) s.insert(dis[i]);
ll ans = 0;
while(!s.empty()){
auto it = s.begin();
if(*it > K) break;
K -= *it;
s.erase(it);
ans++;
}
for(int i = 0; i < n; i++) v[i].clear();
return ans;
}
