#include "closing.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<tuple>
using namespace std;
const int MAX_N=2e5+5;
const long long INF=(1LL<<60);
int n,x,y;
long long k;
vector<pair<int,int>>g[MAX_N];
int ans;
long long bfsdist[MAX_N];
bool takenfrombfs;
bool not43;
void bfs()
{
for(int i=0;i<n;i++)bfsdist[i]=INF;
long long remm=k;
int curanss=0;
bfsdist[x]=0;
bfsdist[y]=0;
set<pair<long long,int>>q;
q.insert({0,x});
q.insert({0,y});
while(q.size())
{
int u,curdist;
tie(curdist,u)=(*(q.begin()));
if(remm>=curdist)
{
remm-=curdist;
curanss++;
}
else break;
q.erase({curdist,u});
for(auto [v,edge]:g[u])
{
long long len=bfsdist[u]+edge;
if(len<bfsdist[v])
{
q.erase({bfsdist[v],v});
bfsdist[v]=len;
q.insert({bfsdist[v],v});
}
}
}
ans=max(ans,curanss);
}
bool onpath[MAX_N];
long long otherval[MAX_N];
bool stat[MAX_N];
int parent[MAX_N];
long long paredge[MAX_N];
long long depth[MAX_N];
long long curdist;
long long distxy;
multiset<long long>s;
multiset<pair<long long,long long>>pairs;
long long rem;
int curans;
void dfs(int u,int par)
{
for(auto [v,edge]:g[u])
{
if(v==par)continue;
depth[v]=depth[u]+edge;
parent[v]=u;
paredge[v]=edge;
dfs(v,u);
}
}
void spread(int u,int par,long long dfsdist)
{
otherval[u]=-curdist+(distxy-curdist);
if(onpath[u])
{
rem-=curdist;
curans++;
s.insert(otherval[u]);
}
else
{
if(curdist+dfsdist<=otherval[u])
{
s.insert(curdist+dfsdist);
s.insert(otherval[u]);
}
else
{
pairs.insert({otherval[u]+curdist+dfsdist,-(curdist+dfsdist)});
}
}
for(auto [v,edge]:g[u])
{
if(onpath[v] or v==par)continue;
spread(v,u,dfsdist+edge);
}
}
void solve()
{
rem=k;
curans=0;
s.clear();
pairs.clear();
for(int i=0;i<n;i++)
{
onpath[i]=0;
stat[i]=0;
}
parent[x]=-1;
paredge[x]=0;
depth[x]=0;
dfs(x,-1);
distxy=depth[y];
if(distxy>2*k)not43=0;
curdist=0;
bool changed=0;
int u=y;
while(u!=-1)
{
onpath[u]=1;
stat[u]=1;
spread(u,parent[u],0);
curdist+=(changed==0 ? +paredge[u] : -paredge[u]);
if(changed==0)
{
if(curdist>distxy-curdist)
{
curdist=distxy-curdist;
changed=1;
}
}
u=parent[u];
}
if(rem<0)return;
long long last=-1;
while(s.size() or pairs.size())
{
if(pairs.size())
{
auto [pribavi,izvadi]=(*pairs.begin());
if(-izvadi<=last)
{
pairs.erase(pairs.find({pribavi,izvadi}));
continue;
}
long long smal1=INF,smal2=INF;
if(s.size()>=2)
{
smal1=(*s.begin());
s.erase(s.find(smal1));
smal2=(*s.begin());
s.insert(smal1);
}
if(pribavi<=smal1+smal2 && pribavi<=rem)
{
rem-=pribavi;
curans+=2;
pairs.erase(pairs.find({pribavi,izvadi}));
s.erase(s.find(-izvadi));
continue;
}
}
if(s.size()==0)break;
long long smal1=(*s.begin());
s.erase(s.find(smal1));
last=smal1;
if(smal1<=rem)
{
rem-=smal1;
curans++;
}
else break;
}
ans=max(ans,curans);
}
int max_score(int N, int X, int Y, long long K,std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
not43=1;
ans=2;n=N;x=X;y=Y;k=K;
for(int i=0;i<n;i++)g[i].clear();
for(int i=0;i<n-1;i++)
{
int u,v,w;
u=U[i];
v=V[i];
w=W[i];
g[u].push_back({v,w});
g[v].push_back({u,w});
}
bfs();
solve();
return ans;
}
