#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

int max_score(int n, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    vector<vector<pair<int,int>>> e(n);
    rep(i,0,n-1) {
        int u=U[i],v=V[i],w=W[i];
        e[u].pb(mp(v,w));
        e[v].pb(mp(u,w));
    }
    vector<ll> dis1(n),dis2(n);
    function<void(int,int,ll,vector<ll>&)> dfs=[&](int u,int f,ll dep,vector<ll>& dis) {
        dis[u]=dep;
        //printf("??? %d\n",u);
        for (auto [v,w]:e[u]) if (v!=f) {
            dfs(v,u,dep+w,dis);
        }
    };
    dfs(X,0,0ll,dis1);
    dfs(Y,0,0ll,dis2);
    map<ll,vector<ll>> grp;
    vector<ll> w;
    for (int i=0;i<n;i++) {
        w.pb(min(dis1[i],dis2[i]));
        //grp[abs(dis1[i]-dis2[i])].pb(min(dis1[i],dis2[i]));
        //printf("!!! %d %lld %lld\n",i,dis1[i],dis2[i]);
    }
    sort(all(w));
    int ans1=0;
    ll s=0;
    for (auto x:w) {
        s+=x;
        if (s<=K) ans1++;
    }
    for (int i=0;i<n;i++) if (dis1[i]+dis2[i]==dis1[Y]) {
        K-=min(dis1[i],dis2[i]);
        grp[abs(dis1[i]-dis2[i])].pb(0);
    } else {
        grp[abs(dis1[i]-dis2[i])].pb(min(dis1[i],dis2[i]));        
    }
    vector<ll> ret{0ll};
    for (auto [d,vc]:grp) {
        sort(all(vc));
        vector<ll> q1,q2,dp;
        for (auto x:vc) if (x<=d) q1.pb(x); else q2.pb(x);
        ll s=0; dp.pb(0);
        for (auto x:q1) { s+=x; dp.pb(s); }
        rep(i,0,SZ(q1)) { s+=d; dp.pb(s); }
        for (auto x:q2) {
            s+=x; dp.pb(s);
            s+=d; dp.pb(s);
        }
        //printf("dp: ");
        //for (auto x:dp) printf("%lld ",x); puts("");
        vector<ll> tmp(SZ(ret)+SZ(dp)-1,1ll<<60);
        rep(p1,0,SZ(ret)) rep(p2,0,SZ(dp)) tmp[p1+p2]=min(tmp[p1+p2],ret[p1]+dp[p2]);
        ret=tmp;
    }
    //for (auto x:ret) printf("%lld ",x); puts("");
    int ans2=0;
    rep(i,1,SZ(ret)) if (ret[i]<=K) ans2++;
    return max(ans1,ans2);
}