#include "closing.h"
#include<bits/stdc++.h>
#define poly vector<ll>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < ll,ll >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
// #define int ll
// #define N 
using namespace std;
void dfs(int k,int fa,poly &dis,vector<vector<pa>> &G)
{
    for (auto [u,w]:G[k])
    {
        if (u==fa) continue;
        dis[u]=dis[k]+w;
        dfs(u,k,dis,G);
    }
}
int max_score(int n, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    // cerr<<"!!!!!!"<<endl;
    poly dx(n,0),dy(n,0);
    vector<vector<pa>>G(n,vector<pa>());
    for (int i=0;i+1<n;i++)
        G[U[i]].push_back(mp(V[i],W[i])),
        G[V[i]].push_back(mp(U[i],W[i]));
    dfs(X,X,dx,G);
    dfs(Y,Y,dy,G);
    // cerr<<"!!!!!!"<<endl;
    int ans=0;
    {
        priority_queue<pa>q;
        vector<bool>vis(n,0);
        for (int i=0;i<n;i++)
            q.push(mp(-dx[i],i)),q.push(mp(-dy[i],i));
        ll sm=0;
        int now=0;
        while (!q.empty())
        {
            int u=q.top().se;
            ll w=-q.top().fi;
            q.pop();
            if (vis[u]) continue;
            vis[u]=1;
            sm+=w;
            if (sm>K) break;
            now++;
        }
        while (!q.empty()) q.pop();
        ans=max(ans,now);
    }
    {
        priority_queue<pair<int,pa>,vector<pair<int,pa>>,greater<pair<int,pa>> >q;
        priority_queue<pair<int,pa>>qs;
        vector<int>vis(n,0);
        vector<poly>val(n,poly(3,-19));
        ll mn=dx[0]+dy[0];
        for (int i=0;i<n;i++)
        {
            if (dx[i]+dy[i]<mn) mn=min(mn,dx[i]+dy[i]);
        }
        int now=0;
        int DFN=0;
        for (int i=0;i<n;i++)
            if (dx[i]+dy[i]==mn) 
            {
                val[i][0]=0;
                K-=min(dx[i],dy[i]),vis[i]=1,val[i][1]=abs(dx[i]-dy[i]),q.push(mp(abs(dx[i]-dy[i]),mp(++DFN,i))),now++;
            }
            else
            {
                vis[i]=0;
                q.push(mp(min(dx[i],dy[i]),mp(++DFN,i)));
                val[i][0]=min(dx[i],dy[i]);
                val[i][1]=abs(dx[i]-dy[i]);
            }
        if (K>=0)
        {
            int tt=0;
            while (!q.empty())
            {
                int u=q.top().se.se;
                ll w=q.top().fi;
                // cout<<"??"<<u<<","<<w<<'\n';
                q.pop();
                // cout<<"?"<<u<<" "<<w<<" "<<DFN<<" "<<now<<" "<<vis[u]<<" "<<val[u][0]<<" "<<val[u][1]<<endl;
                if (w!=val[u][vis[u]]||tt==1000000) continue;
                if (K<w)
                {
                    tt++;
                    pair<int,pa> tmp=mp(-1,mp(-1,-1));
                    while (qs.size()&&
                        (vis[qs.top().se.se]==0||qs.top().fi!=val[qs.top().se.se][vis[qs.top().se.se]-1]
                        ||qs.top().se.se==u)) 
                        {
                            if (qs.top().se.se==u&&!(
                                vis[qs.top().se.se]==0||qs.top().fi!=val[qs.top().se.se][vis[qs.top().se.se]-1]))
                                tmp=qs.top();
                            qs.pop();
                        }
                    if (qs.size()&&K+qs.top().fi-w>=0)
                    {
                        int v=qs.top().se.se;
                        K+=qs.top().fi-w;
                        vis[v]--;
                        qs.pop();
                        qs.push(mp(val[u][vis[u]],mp(++DFN,u)));
                        vis[u]++;
                        if (vis[u]<=1) q.push(mp(val[u][vis[u]],mp(++DFN,u)));
                        q.push(mp(val[v][vis[v]],mp(++DFN,v)));
                    } else
                    {
                        if (tmp.fi!=-1) qs.push(tmp);
                    }
                } else
                {
                    tt=0;
                    K-=w;
                    qs.push(mp(val[u][vis[u]],mp(++DFN,u)));
                    vis[u]++;
                    if (vis[u]<=1) q.push(mp(val[u][vis[u]],mp(++DFN,u)));
                    now++;
                }
            }
            ans=max(ans,now);
        }
    }
    return ans;
}