#include "bits/stdc++.h"
#include "closing.h"
#define pb push_back
using namespace std;
const long long inf = 1e18 + 5;
const int MAXN = 2e5 + 5;
vector<int> curpath, path;
vector<long long> disx(MAXN), disy(MAXN);
vector<pair<int, int> > adj[MAXN];
void dfs(int node, int par, int target){
if(node == target){
path = curpath;
}
for(auto itr: adj[node]){
if(itr.first != par){
curpath.pb(itr.first);
dfs(itr.first, node, target);
curpath.pop_back();
}
}
}
void disc(int node, int par, long long dis, int type){
if(!type) disx[node] = dis;
else disy[node] = dis;
for(auto itr: adj[node]){
if(itr.first != par){
disc(itr.first, node, dis + itr.second, type);
}
}
}
int max_score(int N, int X, int Y, long long 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]].pb({V[i], W[i]});
adj[V[i]].pb({U[i], W[i]});
}
disc(X, X, 0, 0);
disc(Y, Y, 0, 1);
curpath.clear();
path.clear();
dfs(X, X, Y);
priority_queue<long long> pq;
for(int i = 0; i < N; i++){
pq.push({-min(disx[i], disy[i])});
}
int ans = 0;
long long cur = 0;
while(!pq.empty()){
long long val = pq.top() * (-1);
pq.pop();
if(val + cur <= K){
cur += val;
ans++;
}
else break;
}
return ans;
}
