// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define i128 __int128
typedef int iint;
#define int long long
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 600005
#define inf 0x3f3f3f3f

int cardboard_box(vi a,vi b,int k){
	int n=a.size();
	For(i,0,n-1)a.pb(b[i]-a[i]);
	priority_queue<pii,vector<pii>,greater<pii>>q1,q2;
	For(i,0,n-1) q1.push(mkp(a[i],i)),q2.push(mkp(a[i]+a[i+n],i));
	vi vis(n*2,0);
	int res=0;
	For(_,1,n*2){
		while(q1.size() && vis[q1.top().se])q1.pop();
		while(q2.size() && vis[q2.top().se])q2.pop();
		if(res+q1.top().fi>k)return _-1;
		int i=q1.top().se; q1.pop();
		while(q1.size() && vis[q1.top().se])q1.pop();
		if(_!=n*2 && q2.size() && a[i]+q1.top().fi>=q2.top().fi){
			q1.push(mkp(a[i],i));
			i=q2.top().se;
			q2.pop();
		}
		if(i<n) q1.push(mkp(a[i+n],i+n));
		res+=a[i],vis[i]=1;
	}
	return n*2;
}

vector<pii>e[maxn];
int dis1[maxn],dis2[maxn];
void dfs(int u,int pa,int*dis){
	for(auto [v,w]:e[u]){
		if(v==pa)continue;
		dis[v]=dis[u]+w;
		dfs(v,u,dis);
	}
}

iint max_score(iint n,iint s,iint t,int k,vector<iint>U,vector<iint>V,vector<iint>W){
	For(i,0,n-1) e[i].clear();
	For(i,0,n-2) e[U[i]].pb(mkp(V[i],W[i])),e[V[i]].pb(mkp(U[i],W[i]));
	dis1[s]=0,dfs(s,0,dis1);
	dis2[t]=0,dfs(t,0,dis2);
	int sum=0;
	For(i,0,n-1){
		bool on=(dis1[i]+dis2[i]==dis1[t]);
		if(on)sum+=min(dis1[i],dis2[i]);
	}
	int res=0;
	vi c;
	For(i,0,n-1)c.pb(dis1[i]),c.pb(dis2[i]);
	sort(c.begin(),c.end());
	int now=0;
	for(int x:c){
		now+=x;
		if(now>k)break;
		++res;
	}
	if(sum<=k){
		vi a,b;
		For(i,0,n-1){
			bool on=(dis1[i]+dis2[i]==dis1[t]);
			if(on) a.pb(0),b.pb(max(dis1[i],dis2[i])-min(dis1[i],dis2[i]));
			else a.pb(min(dis1[i],dis2[i])),b.pb(max(dis1[i],dis2[i]));
		}
		res=max(res,cardboard_box(a,b,k-sum));
	}
	return res;
}