#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct helper_class {
struct BIT {
private:
vector<int>todie;
ll TRE[1<<20];
int cnt[1<<20];
ll qryvl(int i){
ll res=0;
while(i)
res+=TRE[i],i-=i&-i;
return res;
}
int querycnt(int i){
int res=0;
while(i)res+=cnt[i],
i-=i&-i;
return res;
}
public:
void upd(int i,ll v,int cof){
while(i<1<<20) todie.push_back(i),
cnt[i]+=cof,TRE[i]+=cof*v,i+=i&-i;
}
int howmuch(ll v){
int l=0,r=7e5,res=0;
while(l<=r){
int mid=l+r>>1;
if(qryvl(mid)<=v)
res=mid,l=mid+1;
else r=mid-1;
}
return querycnt(res);
}
void reset(){
for(auto i:todie)
TRE[i]=cnt[i]=0;
todie.clear();
}
} cur;
int operator()(vector<pair<ll,ll>> V,ll K){
cur.reset();
if(K<0) return -1e9;
map<int,int>mp;
for(auto&[i,j]:V)swap(i,j);
sort(V.begin(),V.end());
for(auto&[i,j]:V)swap(i,j);
for(auto[i,j]:V)
mp[i]++,mp[j-i]++;
int ans=0,CC=0,n=V.size();
for(auto&[i,j]:mp)
j=CC+=j;
vector<pair<int,int>> v2;
for(auto[i,j]:V)
v2.push_back({mp[i]--,mp[j-i]--});
for(int i=0;i<n;i++)
cur.upd(v2[i].first,V[i].first,1);
ans=cur.howmuch(K);
for(int i=0;i<n;){K-=V[i].first; if(K<0)break;
cur.upd(v2[i].first,V[i].first,-1);
cur.upd(v2[i].second,V[i].second-V[i].first,1);
ans=max(ans,++i+cur.howmuch(K));
}
return ans;
}
} thecenter;
vector<pair<int,int>>adj[200100];
vector<ll>v;
vector<int>path;
ll dis[200100][2];
void dfs(int n,int p,ll d,int k){
dis[n][k]=d;
v.push_back(d);
for(auto[i,w]:adj[n])
if(i-p)dfs(i,n,d+w,k);
}
int max_score(int N, int X, int Y, ll K,std::vector<int> U, std::vector<int> V, std::vector<int> W){
for(int i=0;i<N-1;i++)
adj[U[i]].push_back({V[i],W[i]}),
adj[V[i]].push_back({U[i],W[i]});
v.clear();
dfs(X,N,0,0);
dfs(Y,N,0,1);
sort(v.rbegin(),v.rend());
ll origK=K;
while(v.size())
if(v.back()<=K)
K-=v.back(),
v.pop_back();
else break;
for(int i=0;i<N;i++)
adj[i].clear();
K=origK;
int ans1=2*N-v.size();
vector<pair<ll,ll>> stuf;
for(int i=0;i<N;i++)
if(dis[i][0]+dis[i][1]==dis[X][1])
K-=min(dis[i][0],dis[i][1]),
stuf.push_back({0,abs(dis[i][0]-dis[i][1])});
else stuf.push_back({min(dis[i][0],dis[i][1]),
max(dis[i][0],dis[i][1])});
return max(ans1,thecenter(stuf,K));
}
