#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
#define ll long long
#define pb push_back
const int N=2e5+5;const ll INF=2e18;
int cnt,z[N];ll a[N],b[N],tmp[N*2];bool tg[N];
struct Edge {int v,w;};vector<Edge> e[N];
struct Node {int x;ll w;bool operator < (Node t) const {return w>t.w;}};
priority_queue<Node> q01,q02,q10,q12,q21;
void dfs(int u,int f) {for(auto [v,w]:e[u]) if(v!=f) a[v]=a[u]+w,dfs(v,u);}
void clear()
{
    while(!q01.empty()) q01.pop();while(!q02.empty()) q02.pop();
    while(!q10.empty()) q10.pop();while(!q12.empty()) q12.pop();
    while(!q21.empty()) q21.pop();
}
void po()
{
    while(!q01.empty() && z[q01.top().x]) q01.pop();
    while(!q02.empty() && z[q02.top().x]) q02.pop();
    while(!q10.empty() && z[q10.top().x]!=1) q10.pop();
    while(!q12.empty() && z[q12.top().x]!=1) q12.pop();
    while(!q21.empty() && z[q21.top().x]!=2) q21.pop();
}
void upd(int x,int y)
{
    z[x]=y;if(!y) q01.push((Node) {x,a[x]}),q02.push((Node) {x,b[x]});
    if(y==1) {if(!tg[x]) q10.push((Node) {x,-a[x]});q12.push((Node) {x,b[x]-a[x]});}
    if(y==2) q21.push((Node) {x,a[x]-b[x]});
}
int max_score(int n,int S,int T,ll m,vector<int> _u,vector<int> _v,vector<int> _w)
{
    int ans=0;ll m1=m;cnt=0;fill(tg,tg+n,0);clear();for(int i=0;i<n;++i) e[i].clear();
    for(int i=0;i<n-1;++i)
        e[_u[i]].pb((Edge) {_v[i],_w[i]}),e[_v[i]].pb((Edge) {_u[i],_w[i]});
    a[S]=0;dfs(S,0);copy(a,a+n,b);a[T]=0;dfs(T,0);
    copy(a,a+n,tmp);copy(b,b+n,tmp+n);sort(tmp,tmp+n*2);
    for(int i=0;i<n*2;++i) {m-=tmp[i];if(m<0) {ans=i;break;}}m=m1;
    for(int i=0;i<n;++i) if(a[i]+b[i]==a[S]) tg[i]=1,++cnt;
    for(int i=0;i<n;++i) {if(a[i]>b[i]) swap(a[i],b[i]);if(tg[i]) m-=a[i];upd(i,tg[i]);}
    if(m>=0) for(int i=0;i<=n*2;++i)
    {
        ll t,t1,t2,t3,t4;po();
        t1=q01.empty()?INF:q01.top().w;t2=q12.empty()?INF:q12.top().w;
        t3=q02.empty() || q10.empty()?INF:q02.top().w+q10.top().w;
        t4=q02.empty() || q21.empty()?INF:q02.top().w+q21.top().w;
        t=min({t1,t2,t3,t4});m-=t;if(m<0) {ans=max(ans,cnt+i);break;}
        if(t==t1) upd(q01.top().x,1);else if(t==t2) upd(q12.top().x,2);
        else if(t==t3) upd(q02.top().x,2),upd(q10.top().x,0);
        else if(t==t4) upd(q02.top().x,2),upd(q21.top().x,1);
    }return ans;
}