#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;
mt19937_64 rnd(time(0));
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);
    }
    {
        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]);
                val[i][1]=abs(dx[i]-dy[i]);
                vis[i]=1;
                now++;
            }
            else
            {
                val[i][0]=min(dx[i],dy[i]);
                val[i][1]=abs(dx[i]-dy[i]);
            }
        if (K>=0)
        {
            priority_queue<pa,vector<pa>,greater<pa>>q;
            priority_queue<pa,vector<pa>,greater<pa>>qs;
            int sm=0;
            // cout<<"!!!!!!"<<endl;
            for (int i=0;i<n;i++)
            {
                if (dx[i]+dy[i]==mn) 
                {
                    val[i][0]=0;
                    val[i][1]=abs(dx[i]-dy[i]);
                    vis[i]=1;
                    q.push(mp(val[i][1],i));
                    // cout<<"!!"<<i<<" "<<abs(dx[i]-dy[i])<<" "<<val[i][1]<<endl;
                }
                else
                {
                    val[i][0]=min(dx[i],dy[i]);
                    val[i][1]=abs(dx[i]-dy[i]);
                    vis[i]=0;
                    q.push(mp(val[i][0],i));
                    // cout<<"??"<<i<<endl;
                    qs.push(mp(val[i][1]+val[i][0],i));
                }
            }
            // cout<<"!!!!!!"<<endl;
            while (1)
            {
                while (q.size()&&(q.top().fi!=val[q.top().se][vis[q.top().se]]
                ||K<q.top().fi)) 
                {
                    // cout<<"ers "<<q.top().fi<<" "<<q.top().se<<'\n';
                    q.pop();
                }
                while (qs.size()&&(vis[qs.top().se]==1||K<val[qs.top().se][0])) qs.pop();
                // cout<<"!!"<<now<<" "<<q.size()<<" "<<qs.size()<<" "<<K<<" "<<endl;
                if (!q.size()&&!qs.size()) break;
                now++;
                // cout<<"!!"<<now<<" "<<q.size()<<" "<<qs.size()<<" "<<K<<" "<<q.top().fi<<endl;
                if (!q.size())
                {
                    int u=qs.top().se;
                    qs.pop();
                    K-=val[u][0];
                    vis[u]++;
                    if (vis[u]<=1)
                        q.push(mp(val[u][vis[u]],u));
                    continue;
                }
                if (!qs.size())
                {
                    int u=q.top().se;
                    q.pop();
                    // cout<<"fill "<<u<<endl;
                    K-=val[u][vis[u]];
                    vis[u]++;
                    if (vis[u]<=1) q.push(mp(val[u][vis[u]],u));
                    continue;
                }
                {
                    int u=q.top().se;
                    int w=q.top().fi;
                    q.pop();
                    vis[u]++;
                    while (q.size()&&(q.top().fi!=val[q.top().se][vis[q.top().se]]
                    ||K<q.top().fi)) q.pop();
                    int www=w;
                    if (q.size()) w+=q.top().fi;
                    vis[u]--;
                    
                    int ww=qs.top().fi;
                    // cout<<"??"<<u<<" "<<w<<" "<<ww<<" "<<K<<'\n';
                    if (w<ww)
                    {
                        K-=val[u][vis[u]];
                        vis[u]++;
                        if (vis[u]<=1) q.push(mp(val[u][vis[u]],u));
                    } else
                    {
                        q.push(mp(www,u));
                        u=qs.top().se;
                        // cout<<"???.."<<u<<" "<<val[u][0]<<" "<<val[u][1]<<endl;
                        qs.pop();
                        K-=val[u][0];
                        vis[u]++;
                        // cout<<"!!!!!!!"<<val[u][vis[u]]<<" "<<u<<'\n';
                        q.push(mp(val[u][vis[u]],u));
                    }
                }
            }          
            ans=max(ans,now);
        }
    }
    return ans;
}