#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 2e18;
struct SegmentTree{
int n, sz;
vector<pair<ll,int>> tree;
void init(int n_) {
n = n_;
sz = 1 << (__lg(n-1) + 1);
tree.resize(sz<<1);
build();
}
void build() {
for (int i=0; i<sz; i++) tree[sz+i] = {inf, i};
for (int i=sz-1; i>=1; i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
};
void ins(int pos, ll val) {
tree[pos+sz] = {val, pos};
for (pos += sz; pos > 1; pos >>= 1)
tree[pos>>1] = min(tree[pos], tree[pos^1]);
}
void del(int tar) { ins(tar, inf); }
pair<ll,int> get_top() { return tree[1]; }
};
SegmentTree xtoa, xtoab, atoab, atox, abtoa;
vector<int> par;
vector<ll> distX, distY;
vector<vector<pair<int,ll>>> adj;
void dfs1(int x, int p) {
for (auto &[y, c] : adj[x]) {
if (y == p) continue;
par[y] = x;
distX[y] = distX[x] + c;
dfs1(y, x);
}
}
void dfs2(int x, int p) {
for (auto &[y, c] : adj[x]) {
if (y == p) continue;
distY[y] = distY[x] + c;
dfs2(y, x);
}
}
void init(int n) {
par.assign(n, 0);
distX.assign(n, 0);
distY.assign(n, 0);
adj.assign(n, vector<pair<int,ll>>());
}
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
init(N);
for (int i=0; i<N-1; i++) {
adj[U[i]].emplace_back(V[i], (ll)W[i]);
adj[V[i]].emplace_back(U[i], (ll)W[i]);
}
par[X] = -1; distX[X] = 0;
dfs1(X, -1);
distY[Y] = 0;
dfs2(Y, -1);
vector<ll> A(N, 0), B(N, 0);
for (int i=0; i<N; i++) {
A[i] = min(distX[i], distY[i]);
B[i] = max(distX[i], distY[i]) - A[i];
}
int ans = 0;
ll sum = 0;
vector<ll> t = A;
sort(t.begin(), t.end());
for (int i=0; i<N; i++) {
sum += t[i];
if (sum > K) break;
ans ++;
}
vector<int> inpath(N, 0);
int x = Y;
int cnt = 0;
while (x != -1) {
inpath[x] = 1;
cnt ++;
x = par[x];
}
vector<ll> cost1(2*cnt+1, 0), cost2(2*(N-cnt)+1, 0);
t.clear();
xtoa.init(N); xtoab.init(N);
atoab.init(N); atox.init(N);
abtoa.init(N);
for (int i=0; i<N; i++) {
if (inpath[i]) {
cost1[cnt] += A[i];
t.push_back(B[i]);
}
else {
xtoa.ins(i, A[i]);
xtoab.ins(i, A[i]+B[i]);
}
}
sort(t.begin(), t.end());
for (int i=0; i<cnt; i++) cost1[cnt+i+1] = cost1[cnt+i] + t[i];
ll cur = 0;
for (int i=1; i<=2*(N-cnt); i++) {
ll t1 = xtoa.get_top().first;
ll t2 = atoab.get_top().first;
ll t3 = xtoab.get_top().first + abtoa.get_top().first;
ll t4 = xtoab.get_top().first + atox.get_top().first;
if (t1 < t2 && t1 < t3 && t1 < t4) {
cur += t1;
int idx = xtoa.get_top().second;
xtoa.del(idx);
xtoab.del(idx);
atoab.ins(idx, B[idx]);
atox.ins(idx, -A[idx]);
}
else if (t2 < t3 && t2 < t4) {
cur += t2;
int idx = atoab.get_top().second;
atoab.del(idx);
atox.del(idx);
abtoa.ins(idx, -B[idx]);
}
else if (t3 < t4) {
cur += t3;
int idx1 = xtoab.get_top().second, idx2 = abtoa.get_top().second;
xtoa.del(idx1);
xtoab.del(idx1);
atoab.ins(idx2, B[idx2]);
atox.ins(idx2, -A[idx2]);
abtoa.ins(idx1, -B[idx1]);
abtoa.del(idx2);
}
else {
cur += t4;
int idx1 = xtoab.get_top().second, idx2 = atox.get_top().second;
xtoa.del(idx1);
xtoa.ins(idx2, A[idx2]);
xtoab.del(idx1);
xtoab.ins(idx2, A[idx2]+B[idx2]);
atoab.del(idx2);
atox.del(idx2);
abtoa.ins(idx1, -B[idx1]);
}
cost2[i] = cur;
}
int j = 0;
for (int i=cnt*2; i>=cnt; i--) {
if (cost1[i] > K) continue;
while (j < (N-cnt)*2 && cost1[i] + cost2[j+1] <= K) j ++;
ans = max(ans, i + j);
}
return ans;
}
