#include<bits/stdc++.h>
//#include "closing.h"
#define MAXN 1000007
using namespace std;
struct event{
long long cost;
int x,type;
inline friend bool operator < (event fr,event sc){
return fr.cost>sc.cost;
}
};
int n,x,y,sz;
vector< pair<int,int> > v[MAXN];
vector< pair<long long,int> > add[2];
long long dist[MAXN][2];
vector<int> path;
int root[MAXN],vis[MAXN],ban[MAXN];
long long init_cost[MAXN];
vector< pair<long long,int> > costs[MAXN];
bool reach[MAXN][2];
void reset(){
for(int i=1;i<=n;i++){
v[i].clear();
vis[i]=ban[i]=0;
init_cost[i]=0;
costs[i].clear();
reach[i][0]=reach[i][1]=false;
}
for(int i=0;i<2;i++){
add[i].clear();
}
path.clear();
}
void dfs(int x,int p,int id,long long d){
dist[x][id]=d;
add[id].push_back({dist[x][id],x});
for(auto nxt:v[x]){
if(nxt.first==p)continue;
dfs(nxt.first,x,id,d+nxt.second);
}
}
bool dfs2(int x,int p,int y){
if(x==y){
path={y};
return true;
}
for(auto nxt:v[x]){
if(nxt.first==p)continue;
if(dfs2(nxt.first,x,y)){
path.push_back(x);
return true;
}
}
return false;
}
void greedy(int r){
long long init=0;
int start=root[r];
for(int i=1;i<=n;i++)vis[i]=0;
for(int i:path){
vis[i]+=1;
if(i==start)break;
init+=dist[i][0];
}
for(int i=path.size()-1;i>=0;i--){
vis[path[i]]+=2;
if(path[i]==start)break;
init+=dist[path[i]][1];
}
init+=max(dist[start][0],dist[start][1]);
init_cost[r]=init;
for(int i=1;i<=n;i++){
if(i==start)continue;
if(vis[i]==0)costs[r].push_back({max(dist[i][0],dist[i][1]),i});
if(vis[i]==1)costs[r].push_back({dist[i][1]-dist[i][0],i});
if(vis[i]==2)costs[r].push_back({dist[i][0]-dist[i][1],i});
}
sort(costs[r].begin(),costs[r].end());
}
int calc_best(long long s){
int res=0;
for(int i=1;i<=n;i++){
if(ban[i]>0 and ban[i]<3)res++;
if(ban[i]==3)res+=2;
}
int ptl=0,ptr=0;
while(ptl<n or ptr<n){
while(ptl<n and ban[add[0][ptl].second]%2==1)ptl++;
while(ptr<n and ban[add[1][ptr].second]>=2)ptr++;
if(ptl<n and (ptr==n or add[0][ptl].first<add[1][ptr].first)){
s-=add[0][ptl].first;
ptl++;
}else{
s-=add[1][ptr].first;
ptr++;
}
if(s<0)break;
res++;
}
return res;
}
priority_queue< event > q;
void dfs3(int x,int p,int id,long long d){
dist[x][id]=d;
q.push({dist[x][id],x,id});
for(auto nxt:v[x]){
if(nxt.first==p)continue;
dfs3(nxt.first,x,id,d+nxt.second);
}
}
void bfs(int x,int id){
for(auto nxt:v[x]){
if(reach[nxt.first][id])continue;
reach[nxt.first][id]=true;
if(vis[nxt.first]>0){
q.push({dist[nxt.first][id] - dist[nxt.first][1-id],nxt.first,id});
}
}
}
int max_score(int N, int X, int Y, long long K,vector<int> U, vector<int> V, vector<int> W){
n=N; x=X+1; y=Y+1;
reset();
for(int i=0;i<n-1;i++){
v[U[i]+1].push_back({V[i]+1,W[i]});
v[V[i]+1].push_back({U[i]+1,W[i]});
}
dfs(x,0,0,0);
dfs(y,0,1,0);
sort(add[0].begin(),add[0].end());
sort(add[1].begin(),add[1].end());
dfs2(y,0,x);
sz=int(path.size());
for(int i=0;i<sz;i++)root[i]=path[i];
//for(int i=0;i<sz;i++)greedy(i);
int ans=0;
/*ans=max(ans,calc_best(K));
for(int r=0;r<sz;r++){
long long curr=K;
curr-=init_cost[r];
if(curr<0)break;
for(int i=1;i<=n;i++)ban[i]=0;
for(int i:path){
ban[i]+=1;
if(i==root[r])break;
}
for(int i=path.size()-1;i>=0;i--){
ban[path[i]]+=2;
if(path[i]==root[r])break;
}
ans=max(ans,calc_best(curr));
for(int f=0;f<costs[r].size();f++){
curr-=costs[r][f].first;
if(curr<0)break;
ban[costs[r][f].second]=3;
ans=max(ans,calc_best(curr));
}
}*/
reach[x][0]=true;
reach[y][1]=true;
dfs3(x,0,0,0);
dfs3(y,0,1,0);
while(!q.empty())q.pop();
for(int i=1;i<=n;i++)vis[i]=0;
int anss=0;
while(!q.empty() and K>0){
event curr=q.top();
q.pop();
if(curr.cost>K)break;
if(vis[curr.x]==3)continue;
bfs(curr.x,curr.type);
if(vis[curr.x]>0){
vis[curr.x]=3;
}else{
vis[curr.x]=curr.type+1;
if(reach[curr.x][1-curr.type])q.push({dist[curr.x][1-curr.type] - curr.cost,1-curr.type});
}
K-=curr.cost; anss++;
}
return max(ans,anss);
}
/*int main(){
cout<<max_score(7, 0, 2, 10, {0, 0, 1, 2, 2, 5}, {1, 3, 2, 4, 5, 6}, {2, 3, 4, 2, 5, 3})<<"\n";
cout<<max_score(4, 0, 3, 20, {0, 1, 2}, {1, 2, 3}, {18, 1, 19})<<"\n";
return 0;
}*/
