#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCK S_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l, int r)
{
return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const ll inf = 1e15+7;
const int mod2 =998244353;
//const ll base=67;
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,r2, center;
ll i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, root, en;
ll el = 19;
ll x,y;
struct ib
{
ll a,b;
};
vector<ll> c;
vector<ib> f;
ll d[2][200001];
ll suff[200001];
vector<ib> v[200001];
vector<ll> vc;
ll cost(ll x)
{
if(x>k)return -n*2 ;
return upper_bound(c.begin(),c.end(),k-x)-c.begin()+dem2;
}
void dfs(int x,int y,int z)
{
for(auto [g,cx]:v[x])
if(g^y)
{
d[z][g]=d[z][x]+cx;
dfs(g,x,z);
}
}
bool cmp(ib x,ib y)
{
return x.a<y.a;
}
int max_score(int N,int X,int Y,ll K,vector<int> U,vector<int>V,vector<int>W)
{
n=N;
x=X;
y=Y;
k=K;
vc.clear();
c.clear();
f.clear();
for(int i=0;i<n;i++)v[i].clear();
for(int i=0; i<U.size(); i++){
v[U[i]].pb({V[i],W[i]}),
v[V[i]].pb({U[i],W[i]});
}
d[0][x]=d[1][y]=0;
dfs(x,x,0);
dfs(y,y,1);
dem=0;
for(int i=0; i<n; i++)
{
vc.pb(d[0][i]);
vc.pb(d[1][i]);
}
sort(vc.begin(),vc.end());
for(auto x:vc)
{
if(s4+x<=k)
{
s4+=x;
dem++;
}
else
{
break;
}
}
s4=0;
for(int i=0; i<n; i++)
{
int minn=min(d[0][i],d[1][i]);
int maxx=max(d[0][i],d[1][i]);
if(minn+maxx==d[0][y])
{
s4+=minn;
c.pb(maxx-minn);
dem2++;
}
else
if(maxx-minn>=minn)
{
c.pb(maxx-minn);
c.pb(minn);
}
else
{
f.pb({maxx,minn});
}
}
sort(c.begin(),c.end());
for(int i=1; i<c.size(); i++)
c[i]+=c[i-1];
sort(f.begin(),f.end(),cmp);
dem=max(dem,cost(s4));
suff[f.size()]=k+1;
for(int i=f.size()-1; i>=0; --i)
suff[i]=min(suff[i+1],f[i].b);
for(int i=0; i<f.size(); i++)
{
s4+=f[i].a;
s5=max(s5,f[i].a-f[i].b);
dem=max(dem,cost(s4-s5)+i*2+1);
dem=max(dem,cost(s4)+i*2+2);
dem=max(dem,cost(s4+suff[i+1])+i*2+3);
}
return dem;
}
