#include <bits/stdc++.h>
using namespace std;
#include "closing.h"
//#define int long long
using ll = long long;
#define pi pair<ll, ll>
#define pii pair<ll, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll e[200005];
struct node{
int s, e, m;
ll val, cnt;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
if(s != e)l = new node(s, m), r = new node(m + 1, e);
val = cnt = 0;
}
void upd(ll p, ll v){
if(s == e){
val += v;
cnt += (v > 0 ? 1 : -1);
}
else{
if(p <= m)l->upd(p, v);
else r->upd(p, v);
}
}
ll fd(ll x){
if(s == e)return s;
else if(l->val <= x)return r->fd(x - l->val);
else return l->fd(x);
}
ll qry(int a, int b){
if(a == s && b == e)return cnt;
if(b <= m)return l->qry(a, b);
if(a > m)return r->qry(a, b);
else return l->qry(a, m) + r->qry(m + 1, b);
}
ll qv(int a, int b){
if(a == s && b == e)return val;
if(b <= m)return l->qv(a, b);
if(a > m)return r->qv(a, b);
else return l->qv(a, m) + r->qv(m + 1, b);
}
}*root;
ll a[200005], b[200005], p[200005], vs[200005], pa[200005], pb[200005];
vector <pi> adj[200005];
vector <ll> dis;
ll f(int x){
return lower_bound(dis.begin(), dis.end(), x) - dis.begin() + 1;
}
ll r(int x){
if(x > (int)dis.size())return 1e18;
return dis[x - 1];
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
ll x = X, y = Y;
vector <ll> v;
for(int i = 0; i < N; i++)vs[i] = 0;
for(int i = 0; i < N - 1; i++)e[i + 1] = W[i];
for(int i = 1; i < N; i++)e[i] += e[i - 1];
for(int i = 0; i < N; i++){
a[i] = (i >= x ? e[i] - e[x] : e[x] - e[i]);
b[i] = (i >= y ? e[i] - e[y] : e[y] - e[i]);
}
p[0] = max(a[0], b[0]);
for(int i = 1; i < N; i++)p[i] = p[i - 1] + max(a[i], b[i]);
pa[0] = a[0], pb[0] = b[0];
for(int i = 1; i < N; i++)pa[i] = pa[i - 1] + a[i], pb[i] = pb[i - 1] + b[i];
for(int i = 0; i < N; i++){
//cerr << a[i] << ' ' << b[i] << ' ' << pa[i] << ' ' << pb[i] << ' ' << p[i] << '\n';
}
dis.clear();
for(int i = 0; i < N; i++){
dis.push_back(a[i]); dis.push_back(b[i]);
}
sort(dis.begin(), dis.end());
dis.erase(unique(dis.begin(), dis.end()), dis.end());
root = new node(0, (int)dis.size() + 5);
for(int i = y + 1; i < N; i++)root->upd(f(b[i]), b[i]);
ll ans = 0;
for(int i = 0; i <= y; i++){
for(int j = max(x, 1ll * i); j < N; j++){
ll lol = (j - i + 1) * 2;
ll cur = p[j] - (i == 0 ? 0 : p[i - 1]);
if(j < y)cur += pb[y] - pb[j], lol += y - j;
if(i > x)cur += pa[i - 1] - (x == 0 ? 0 : pa[x - 1]), lol += i - x;
if(j > y)root->upd(f(b[j]), -b[j]);
if(cur > K)continue;
//cerr << j << ' ';
int tmp = root->fd(K - cur), res = root->qv(0, tmp);
//cerr << j << ' ' << tmp << ' ' << (int)dis.size() << ' ';
ans = max(ans, lol + root->qry(0, tmp) + min((tmp == (int)dis.size() + 5? 0 : root->qry(tmp + 1, tmp + 1)), (K - cur - res) / r(tmp + 1)));
//cerr << j << ' ';
}
for(int j = y + 1; j < N; j++)root->upd(f(b[j]), b[j]);
if(i < x)root->upd(f(a[i]), a[i]);
}
for(int i = 0; i < N - 1; i++){
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
vs[X] = vs[Y] = 1;
priority_queue <pi, vector <pi>, greater <pi> > pq;
for(auto [i, j] : adj[X]){
if(!vs[i])pq.push({j, i});
}
for(auto [i, j] : adj[Y]){
if(!vs[i])pq.push({j, i});
}
ll ans2 = 2, cur1 = 0;
while(!pq.empty()){
ll t1 = pq.top().fi, t2 = pq.top().se; pq.pop();
if(vs[t2])continue;
if(cur1 + t1 > K)break;
cur1 += t1; ans2++;
vs[t2] = 1;
for(auto [i, j] : adj[t2]){
if(!vs[i])pq.push({t1 + j, i});
}
}
for(int i = 0; i < N; i++){
adj[i].clear();
}
return max(ans, ans2);
}
