#include "closing.h"
/**
* Author: Nicholas Winschel
* Created: 08.31.2023 14:51:13
**/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
#include <vector>
int max_score(int N, int X, int Y, long long K,
std::vector<int> u, std::vector<int> v, std::vector<int> W)
{
// assume cannot/optimal not to reach common vertex
// overestimates cost in the case that it is possible and optimal
// swap(u,v);
ll oK = K;
V<vi> adj(N);
for (int i = 0; i < N-1; i++) {
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
}
struct op {
ll c;
int v, p;
op () {}
op(ll c, int v, int p) : c(c), v(v), p(p) {}
bool operator<(const op b) const {
return c < b.c;
}
bool operator>(const op b) const {
return c > b.c;
}
};
priority_queue<op, V<op>, greater<op>> pq;
pq.emplace(0,X,-1);
pq.emplace(0,Y,-1);
int ans1 = 0;
while (sz(pq)) {
op e = pq.top();
pq.pop();
if (e.c > K) continue;
K -= e.c;
ans1++;
for (int i : adj[e.v]) {
int x = u[i] == e.v ? v[i] : u[i];
if (x == e.p) continue;
pq.emplace(e.c+W[i],x,e.v);
}
}
K = oK;
vl dist1(N), dist2(N);
auto dfs = [&](int vv, int p, ll d, vl &a, auto &&dfs) -> void {
a[vv] = d;
for (int i : adj[vv]) {
int x = u[i] == vv ? v[i] : u[i];
if (x == p) continue;
dfs(x, vv, d+W[i], a, dfs);
}
};
dfs(X, -1, 0, dist1, dfs);
dfs(Y, -1, 0, dist2, dfs);
// for (auto x : dist1) cerr << x << " ";
//cerr << "\n";
// for (auto x : dist2) cerr << x << " ";
//cerr << "\n";
ll btw = dist2[X];
V<bool> done(2*N);
using sins = tuple<ll, int, int>; // cost, op, prev
using dins = tuple<ll, int, int, int>; // cost, op1, op2, prev
priority_queue<sins, V<sins>, greater<sins>> q1;
priority_queue<dins, V<dins>, greater<dins>> q2;
int ans = 0;
auto perform = [&](int op, int prev) {
//cerr << "dbg: " << K << " " << op << " " << prev << "\n";
int vert = op >= N ? op - N : op;
assert(!done[op]);
ans++;
if ((op < N) != (dist1[vert] <= dist2[vert])) { // NO KIDS
done[op] = true;
} else {
done[op] = true;
ll cu = abs(dist2[vert]-dist1[vert]);
q1.emplace(cu, N-(op-vert) + vert, vert); // opposite
bool b = (dist2[vert] >= dist1[vert]);
for (int i : adj[vert]) {
int x = u[i] == vert ? v[i] : u[i];
if (x == prev) continue;
if ((dist2[x] >= dist1[x]) != b) continue;
q1.emplace(min(dist1[x], dist2[x]), x + op - vert, vert); // child
q2.emplace(max(dist1[x], dist2[x]), x, x+N, vert); // both child
for (int j : adj[x]) { // this is only OK because we are in a tree...
int y = u[j] == x ? v[j] : u[j];
if (y == vert) continue;
if ((dist2[y] >= dist1[y]) != b) continue;
q2.emplace(min(dist1[x], dist2[x]) + min(dist1[y], dist2[y]),
x + op - vert,
y + op - vert,
vert);
}
}
}
};
for (int i = 0; i < N; i++) {
if (dist1[i] + dist2[i] == btw) {
if (dist1[i] <= dist2[i]) {
K -= dist1[i];
perform(i, -1);
} else {
K -= dist2[i];
perform(i + N, -1);
}
}
}
if (K < 0) return ans1;
//cerr << "???\n";
//cerr << sz(q1) << " " << sz(q2) << "\n";
while (sz(q1) || sz(q2)) {
while (q2.size()) {
auto [cu, fi, se, pre] = q2.top();
if (done[fi] || done[se] || cu > K) {
//cerr << "popping q2: " << cu << " " << fi << " " << se << " " << pre << "\n";
q2.pop();
// //cerr << "Popped q2!\n";
} else break;
}
while (q1.size()) {
auto [cu, op, pre] = q1.top();
if (done[op] || cu > K) {
//cerr << "popping q1: " << cu << " " << op << " " << pre << "\n";
q1.pop();
// //cerr << "Popped q1!\n";
} else break;
}
//cerr << "body\n";
if (q1.size() && !q2.size()) {
//cerr << "path1\n";
auto [cu, op, pre] = q1.top();
q1.pop();
K -= cu;
perform(op, pre);
} else if (q2.size()) {
//cerr << "path2\n";
assert(q1.size());
auto o1 = q1.top();
q1.pop();
while (q1.size()) {
auto [cu, op, pre] = q1.top();
if (done[op] || cu > K) {
q1.pop();
} else break;
}
auto ob = q2.top();
if (sz(q1)) { // not given
auto [cu1, op1, pre1] = o1;
auto o2 = q1.top();
auto [cu2, op2, pre2] = o2;
// q1.pop();
auto [cub, fi, se, preb] = ob;
if (cub <= cu1 + cu2) {
q2.pop();
K -= cub;
perform(fi, preb);
perform(se, fi >= N ? fi - N : fi);
q1.push(o1);
// q1.push(o2);
} else {
K -= cu1;
perform(op1, pre1);
// q1.push(o2);
// q2.push(ob);
}
} else {
q1.push(o1);
auto [cub, fi, se, preb] = ob;
q2.pop();
K -= cub;
perform(fi, preb);
perform(se, fi >= N ? fi - N : fi);
}
}
}
return max(ans, ans1);
}
