// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include "closing.h"
#include <bits/stdc++.h>
// #define int long long
#define i64 long long
#define pii pair <i64, i64> 
using namespace std;
vector <pii> E[200005];
i64 depx[200005],depy[200005];
i64 sig[400005],cnt1,cnt2;
pii val[200005];
inline void dfs(int x,int f,i64*dep) {
    for(pii e : E[x]) {
        if(e.first==f) continue;
        dep[e.first]=dep[x]+e.second;
        dfs(e.first,x,dep);
    }
} 
inline void check(int&R,i64&sum,i64 lim) { while(sum>lim) sum-=sig[R--]; }
int max_score(int n, int x, int y,i64 k, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    for(int i=0; i<n; ++i) E[i].clear();
    int m=U.size();
    for(int i=0; i<m; ++i) E[U[i]].emplace_back(V[i],W[i]);
    for(int i=0; i<m; ++i) E[V[i]].emplace_back(U[i],W[i]);
    dfs(x,-1,depx);
    dfs(y,-1,depy);
    for(int i=0,a,b; i<n; ++i) {
        if(depx[i]>depy[i]) a=depy[i],b=depx[i]-a; 
        else                a=depx[i],b=depy[i]-a;
        if(a<b) sig[++cnt1]=a,sig[++cnt1]=b;
        else    val[++cnt2]=(pii){a+b,a};
    }
    sort(val+1,val+cnt2+1);
    sort(sig+1,sig+cnt1+1);
    int R=0; i64 sum=0; sig[cnt1+1]=k+1;
    while(sum+sig[R+1]<=k) sum+=sig[++R];
    int Ans=R;
    for(int i=1; i<=cnt2; ++i) {
        check(R,sum,k-val[i].second),Ans=max(Ans,2*i+R-1);
        check(R,sum,k-=val[i].first),Ans=max(Ans,2*i+R);
    } 
    return Ans;
}
// signed main() {
//     // freopen("localinput","r",stdin);
//     // freopen("localoutput","w",stdout);

//     // fprintf(stderr,"%.4lf\n",1.0*clock()/CLOCKS_PER_SEC);
//     return 0;
// }