#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
vector <pair <int, int>> ke[200001];
long long d[200001][2],cur;
int p[200001],ch[200001];
priority_queue <pair <long long, int>, vector <pair <long long, int>>, greater <pair <long long, int>>> q;
void dfs(int u, int i, int par=-1){
for (auto [v,w]:ke[u])
if (v!=par){
d[v][i]=d[u][i]+w;
p[v]=u;
dfs(v,i,u);
}
}
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-1;i++){
ke[U[i]].push_back({V[i],W[i]});
ke[V[i]].push_back({U[i],W[i]});
}
memset(ch,0,sizeof(ch));
d[X][0]=d[Y][1]=0;
dfs(X,0);
dfs(Y,1);
for (;X!=Y;X=p[X])
ch[X]=1;
ch[Y]=1;
int res=0,cnt=0;
for (int i=0;i<N;i++)
q.push({min(d[i][0],d[i][1]),i});
cur=0;
while (!q.empty()&&cur+q.top().first<=K){
cur+=q.top().first;
res++;
q.pop();
}
while (!q.empty())
q.pop();
cur=0;
for (int i=0;i<N;i++){
if (ch[i]){
q.push({abs(d[i][0]-d[i][1])*2,i});
cur+=min(d[i][0],d[i][1]);
cnt++;
}
else
q.push({max(d[i][0],d[i][1]),i});
}
while (!q.empty()&&cur+q.top().first<=K){
int u=q.top().second;
cur+=q.top().first/(2-ch[u]);
cnt+=2-ch[u];
ch[u]=-1;
q.pop();
}
while (!q.empty())
q.pop();
for (int i=0;i<N;i++)
if (!ch[i])
q.push({min(d[i][0],d[i][1]),1});
while (!q.empty()&&cur+q.top().first<=K){
cur+=q.top().first;
cnt++;
q.pop();
}
while (!q.empty())
q.pop();
for (int i=0;i<N;i++)
ke[i].clear();
return max(res,(cur>K?0:cnt));
}
