#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;
set<pair<long long,int>>s;
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],-u});
}
else s.insert({curdist+dfsdist,u});
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();
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;
while(s.size())
{
auto [grab,u]=(*(s.begin()));
s.erase({grab,u});
u=abs(u);//
if(rem>=grab)
{
rem-=grab;
curans++;
if(stat[u]==0)
{
s.insert({otherval[u],u});
stat[u]=1;
}
}
else break;
}
if(curans>ans)takenfrombfs=0;
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});
}
int maxdeg=0;
for(int i=0;i<n;i++)
{
maxdeg=max(maxdeg,(int)g[i].size());
}
if(maxdeg<=2)not43=0;
takenfrombfs=1;
bfs();
solve();
if(not43 && !takenfrombfs && ans==5)ans++;
return ans;
}
