#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int INF=2e18;
int n,k;
vector<ii> al[200005];
int w[2][200005];
void dfs(int i,int p,int ww,int idx){
w[idx][i]=ww;
for (auto [it,www]:al[i]){
if (it==p) continue;
dfs(it,i,ww+www,idx);
}
}
vector<int> s,b;
vector<int> ps,pb;
int banidx;
int gb(int i){
if (banidx<=i) return b[i+1];
else return b[i];
}
int gpb(int i){
if (banidx<=i) return pb[i+1]-b[banidx];
else return pb[i];
}
ii get(int v){
ii res;
int lo=0,hi=sz(s),mi;
while (hi-lo>1){
mi=hi+lo>>1;
if (s[mi]<=v/2) lo=mi;
else hi=mi;
}
res.fi=lo;
lo=0,hi=sz(b)-(banidx!=INF),mi;
while (hi-lo>1){
mi=hi+lo>>1;
if (gb(mi)<=v) lo=mi;
else hi=mi;
}
res.se=lo;
return res;
}
vector<int> V;
int get(int lim,int ban){
if (lim<0) return -INF;
if (ban==INF) banidx=INF;
else banidx=lb(all(b),ban)-b.begin();
//cout<<"debug: "<<lim<<" "<<ban<<endl;
//rep(x,0,sz(s)) cout<<ps[x]<<" "; cout<<endl;
//rep(x,0,sz(b)-1) cout<<gpb(x)<<" "; cout<<endl;
int lo=0,hi=sz(V),mi;
while (hi-lo>1){
mi=hi+lo>>1;
auto temp=get(V[mi]);
if (ps[temp.fi]+gpb(temp.se)<=lim) lo=mi;
else hi=mi;
}
hi=V[lo+1];
lo=V[lo];
auto t1=get(lo),t2=get(hi);
int si=t1.fi,bi=t1.se;
lim-=ps[si]+gpb(bi);
int temp=min(lim/hi,t2.se-t1.se);
lim-=temp*hi;
bi+=temp;
if (hi>=2){
temp=min(lim/(hi/2),t2.fi-t1.fi);
lim-=temp*(hi/2);
si+=temp;
}
if (lim-s[si+1]>=0) return si+bi*2+1;
if (lim+s[si]-gb(bi+1)>=0) return si+bi*2+1;
return si+bi*2;
}
signed max_score(signed N, signed X, signed Y, int K,
vector<signed> UU, vector<signed> VV, vector<signed> WW){
n=N,k=K;
rep(x,0,n) al[x].clear();
s.clear(),b.clear();
rep(x,0,n-1){
al[UU[x]].pub({VV[x],WW[x]});
al[VV[x]].pub({UU[x],WW[x]});
}
dfs(X,-1,0,0);
dfs(Y,-1,0,1);
rep(x,0,n){
if (w[0][x]>w[1][x]) swap(w[0][x],w[1][x]);
w[1][x]-=w[0][x];
}
//rep(x,0,n) cout<<w[0][x]<<" "; cout<<endl;
//rep(x,0,n) cout<<w[1][x]<<" "; cout<<endl;
vector<int> v;
rep(x,0,n) v.pub(w[0][x]);
sort(all(v));
int ans=0,curr=0;
while (ans<n && curr+v[ans]<=k) curr+=v[ans],ans++;
int d=w[1][X],extra=0;
rep(x,0,n){
if (2*w[0][x]+w[1][x]==d){
k-=w[0][x];
s.pub(w[1][x]);
extra++;
}
else if (w[0][x]<=w[1][x]) s.pub(w[0][x]),s.pub(w[1][x]);
else b.pub(w[0][x]+w[1][x]);
}
s.pub(0),s.pub(INF);
b.pub(0),b.pub(INF);
sort(all(s));
sort(all(b));
V={0};
for (auto it:s) V.pub(it*2);
for (auto it:b) V.pub(it);
sort(all(V));
V.erase(unique(all(V)),V.end());
//for (auto it:s) cout<<it<<" "; cout<<endl;
//for (auto it:b) cout<<it<<" "; cout<<endl;
//for (auto it:V) cout<<it<<" "; cout<<endl;
ps=s,pb=b;
rep(x,1,sz(ps)) ps[x]+=ps[x-1];
rep(x,1,sz(pb)) pb[x]+=pb[x-1];
ans=max(ans,extra+get(k,INF));
rep(x,0,n) if (2*w[0][x]+w[1][x]!=d && w[0][x]>w[1][x]){
ans=max(ans,extra+get(k-w[0][x],w[0][x]+w[1][x])+1);
}
return ans;
}
