#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];
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];
int parent[MAX_N];
long long paredge[MAX_N];
long long depth[MAX_N];
long long curdist;
long long distxy;
long long rem;
int curans;
multiset<long long>s;
vector<long long>best[MAX_N][2];
long long dp[2][MAX_N][3];
int sz;
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)
{
if(dfsdist)s.insert(curdist+dfsdist);
else
{
rem-=curdist;
curans++;
}
for(auto [v,edge]:g[u])
{
if(onpath[v] or v==par)continue;
spread(v,u,dfsdist+edge);
}
}
void solve()
{
rem=k;
curans=0;
for(int i=0;i<n;i++)
{
onpath[i]=0;
}
sz=0;
parent[x]=-1;
paredge[x]=0;
depth[x]=0;
dfs(x,-1);
distxy=depth[y];
curdist=0;
bool changed=0;
int u=y;
while(u!=-1)
{
onpath[u]=1;
s.clear();
spread(u,parent[u],0);
++sz;
int all=s.size()+1;
best[sz][0].clear();
best[sz][0].push_back(0);
for(auto D:s)
{
best[sz][0].push_back(best[sz][0].back()+D);
}
best[sz][1].resize(2*all);
best[sz][1][0]=0;
for(long long take=1;take<=2*all-1;take++)
{
best[sz][1][take]=INF;
for(long long subtake=0;subtake<=min((long long)best[sz][0].size()-1,take);subtake++)
{
if(take-subtake<=subtake+1)best[sz][1][take]=min(best[sz][1][take],best[sz][0][subtake]+(take-subtake)*(-curdist+(distxy-curdist)));
}
}
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;
for(int take=1;take<=2*n-curans;take++)
{
for(int f=0;f<3;f++)
{
dp[0][take][f]=INF;
}
}
for(int i=1;i<=sz;i++)
{
for(int take=1;take<=2*n-curans;take++)
{
for(int f=0;f<3;f++)
{
for(int subtake=0;subtake<=min(take,(int)best[i][(f==1)].size()-1);subtake++)
{
dp[i&1][take][f]=min(dp[i&1][take][f],min(dp[(i-1)&1][take-subtake][f],(f>0 ? dp[(i-1)&1][take-subtake][f-1] : INF))+best[i][(f==1)][subtake]);
}
}
}
for(int take=1;take<=2*n-curans;take++)
{
for(int f=0;f<3;f++)
{
dp[(i-1)&1][take][f]=INF;
}
}
}
for(int take=2*n-curans;take>=0;take--)
{
if(min(dp[sz&1][take][0],min(dp[sz&1][take][1],dp[sz&1][take][2]))<=rem)
{
curans+=take;
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)
{
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;
}
