#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
const ll inf = 2e18;
vector<pair<int, ll>> adj[MAXN];
ll dx[MAXN], dy[MAXN], d1[MAXN], d2[MAXN], ss[MAXN << 1], sd[MAXN << 1];
void dfs(int x, int par, ll dist, ll *darr){
darr[x] = dist;
for (auto [nn, nd] : adj[x]){
if (nn == par) continue;
dfs(nn, x, dist + nd, darr);
}
}
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
for (int i = 0; i < N; i++) adj[i].clear();
for (int i = 0; i < N - 1; i++){
int u = U[i], v = V[i], w = W[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(X, -1, 0, dx); dfs(Y, -1, 0, dy);
for (int i = 0; i < N; i++){
d1[i] = min(dx[i], dy[i]);
d2[i] = max(dx[i], dy[i]) - d1[i];
}
int ans1 = 0, ans2 = 0;
ll cap = K;
vector<ll> vl1(N);
for (int i = 0; i < N; i++) vl1[i] = d1[i];
sort(vl1.begin(), vl1.end());
for (ll c : vl1){
if (cap < c) break;
cap -= c; ans1++;
}
cap = K;
vector<ll> vs;
vector<pair<ll, int>> vd;
set<pair<ll, int>> reg;
for (int i = 0; i < N; i++){
if (dx[i] + dy[i] == dx[Y]){
cap -= d1[i]; ans2++;
vs.push_back(d2[i]);
}
else if (d1[i] > d2[i]){
vd.push_back({d1[i] + d2[i], i});
reg.insert({d1[i], i});
}
else{
vs.push_back(d1[i]);
vs.push_back(d2[i]);
}
}
if (cap >= 0){
sort(vs.begin(), vs.end()); sort(vd.begin(), vd.end());
int ssz = vs.size(), dsz = vd.size();
ss[0] = 0;
for (int i = 0; i < ssz; i++) ss[i + 1] = ss[i] + vs[i];
ll sub = 0;
sd[0] = 0;
for (int i = 0; i < dsz; i++){
ll c; int id; tie(c, id) = vd[i];
ll r1a2 = c - sub, a1 = inf;
if (!reg.empty()) a1 = reg.begin()->first;
sd[(i << 1) + 1] = sd[i << 1] + min(r1a2, a1);
sd[(i << 1) + 2] = sd[i << 1] + c;
sub = max(sub, d2[id]);
reg.erase({d1[id], id});
}
int res = 0;
for (int si = 0, di = (dsz << 1); si <= ssz; si++){
while (di > 0 && ss[si] + sd[di] > cap) di--;
if (ss[si] + sd[di] > cap) break;
res = max(res, si + di);
}
ans2 += res;
}
else ans2 = 0;
return max(ans1, ans2);
}
