// #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];
i64 vvv[400005];
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) { if(lim<0) return R=-1000000,void(); 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(); cnt1=cnt2=0; int k0=k;
    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; i<n; ++i) cerr<<depx[i]<<' '; cerr<<endl;
    // for(int i=0; i<n; ++i) cerr<<depy[i]<<' '; cerr<<endl;
    int cnt=0;
    for(int i=0,a,b; i<n; ++i) {
        vvv[i+1]=depx[i];
        vvv[i+n+1]=depy[i];
        if(depx[i]+depy[i]==depx[y]) {
            k-=min(depx[i],depy[i]);
            sig[++cnt1]=max(depx[i],depy[i]);
            ++cnt;
            continue;
        }
        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);
    sort(vvv+1,vvv+2*n+1); vvv[2*n+1]=k0+1;
    int p=0; i64 s1=0; 
    while(s1+vvv[p+1]<=k0) s1+=vvv[++p];
    int Ans=p;
    // cerr<<Ans<<"----------"<<endl;
    // for(int i=1; i<=cnt1; ++i) cerr<<sig[i]<<' '; cerr<<endl;
    // for(int i=1; i<=cnt2; ++i) cerr<<val[i].first<<' '<<val[i].second<<'|'; cerr<<endl;
    int R=0; i64 sum=0; sig[cnt1+1]=k+1;
    while(sum+sig[R+1]<=k) sum+=sig[++R];
    // cerr<<R<<' '<<sum<<endl;
    if(k>=0) Ans=max(Ans,R+cnt);
    // cerr<<"------------------"<<endl;
    if(k>=0) for(int i=1; i<=cnt2; ++i) {
        check(R,sum,k-val[i].second),Ans=max(Ans,2*i+R+cnt-1);
        check(R,sum,k-=val[i].first),Ans=max(Ans,2*i+R+cnt);
    } 
    return Ans;
}