#include "closing.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<tuple>
#include<map>
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 d[MAX_N];
bool takenfrombfs;
bool not43;
void bfs()
{
for(int i=0;i<n;i++)d[i]=INF;
long long remm=k;
int curanss=0;
d[x]=0;
d[y]=0;
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({0,x});
q.push({0,y});
while(q.size())
{
int v = q.top().second;
int d_v = q.top().first;
q.pop();
if (d_v != d[v])
continue;
if(remm>=d_v)
{
remm-=d_v;
curanss++;
}
else break;
q.pop();
for (auto [to,len] : g[v])
{
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
q.push({d[to], to});
}
}
}
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;
vector<long long>s;
vector<pair<long long,long long>>pairs;
map<long long,int>skiped;
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.push_back(otherval[u]);
}
else
{
if(curdist+dfsdist<=otherval[u])
{
s.push_back(curdist+dfsdist);
s.push_back(otherval[u]);
}
else
{
pairs.push_back({otherval[u]+curdist+dfsdist,-(curdist+dfsdist)});
s.push_back(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();
skiped.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;
sort(pairs.begin(),pairs.end());
sort(s.begin(),s.end());
int sz=pairs.size();
int pos=0;
int Ssz=s.size();
int Spos=0;
long long last=-1;
long long smal1,smal2,smal;
long long pribavi,izvadi;
while(Ssz>0 or sz>0)
{
if(sz>0)
{
tie(pribavi,izvadi)=pairs[pos];
if(-izvadi<=last)
{
pos++;
sz--;
continue;
}
smal1=INF;
smal2=INF;
if(Ssz>=2)
{
smal1=s[Spos];
smal2=s[Spos+1];
}
if(pribavi<=smal1+smal2 && pribavi<=rem)
{
rem-=pribavi;
curans+=2;
pos++;
sz--;
skiped[-izvadi]++;
continue;
}
}
if(Ssz==0)break;
smal=s[Spos];
if(skiped.find(smal)!=skiped.end())
{
if(skiped[smal]>0)
{
Ssz--;
Spos++;
skiped[smal]--;
continue;
}
}
Ssz--;
Spos++;
last=smal;
if(smal<=rem)
{
rem-=smal;
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;
}
