#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> _W)
{
vector<vector<pair<int, int>>> adj(N);
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]});
}
vector<int> line;
vector<int> idx(N);
vector<vector<int>> W(2, vector<int>(N));
{
int p = -1;
int v;
for (int i = 0; i < N; ++i) {
if ((int)adj[i].size() == 1) {
v = i;
break;
}
}
line.push_back(v);
while (true) {
bool ok = false;
for (auto& [u, w] : adj[line.back()]) {
if (u == p) continue;
p = line.back();
line.push_back(u);
ok = true;
break;
}
if (!ok) break;
}
assert((int)line.size() == N);
for (int i = 0; i < N; ++i) {
idx[line[i]] = i;
}
int id = idx[X];
while (id > 0) {
int now = line[id];
int to = line[id - 1];
for (auto& [u, w] : adj[now]) {
if (u == to) {
W[0][id - 1] = w;
}
}
id--;
}
id = idx[X];
while (id + 1 < N) {
int now = line[id];
int to = line[id + 1];
for (auto& [u, w] : adj[now]) {
if (u == to) {
W[0][id + 1] = w;
}
}
id++;
}
id = idx[Y];
while (id > 0) {
int now = line[id];
int to = line[id - 1];
for (auto& [u, w] : adj[now]) {
if (u == to) {
W[1][id - 1] = w;
}
}
id--;
}
id = idx[Y];
while (id + 1 < N) {
int now = line[id];
int to = line[id + 1];
for (auto& [u, w] : adj[now]) {
if (u == to) {
W[1][id + 1] = w;
}
}
id++;
}
}
int res = 0;
// cout << "\nline = ";
// for (int i = 0; i < N; ++i) {
// cout << line[i] << " ";
// }
// cout << "\n";
// cout << "X weights = ";
// for (int i = 0; i < N; ++i) {
// cout << W[0][i] << " ";
// }
// cout << "\n";
// cout << "Y weights = ";
// for (int i = 0; i < N; ++i) {
// cout << W[1][i] << " ";
// }
// cout << "\n";
cerr << idx[X] << " " << idx[Y] << "\n";
for (int left = 0; left < N; ++left) {
ll sum = 0;
ll curr = 0;
vector<ll> C(N), ps(N);
int now = left + 1;
int id = idx[X];
bool ok = true;
for (int it = 0; it <= left; ++it) {
if (id < 0) {
ok = false;
break;
}
curr += W[0][id];
if (sum + curr - C[id] > K) {
ok = false;
break;
}
sum += curr - C[id];
C[id] = curr;
ps[id] = curr;
id -= 1;
}
if (!ok) continue;
curr = 0;
id = idx[X];
vector<array<ll, 3>> rollback;
int leftid = idx[Y], rightid = idx[Y];
ll leftsum = 0, rightsum = 0;
now += 1;
while (true) {
ll take_left = K, take_right = K;
if (leftid - 1 >= 0) {
take_left = max(0LL, leftsum + W[1][leftid - 1] - C[leftid - 1]);
}
if (rightid + 1 < N) {
take_right = max(0LL, rightsum + W[1][rightid + 1] - C[rightid + 1]);
}
if (sum + min(take_left, take_right) > K) {
break;
}
if (take_left < take_right) {
sum += take_left;
rollback.push_back({0, C[leftid - 1], take_left});
leftsum += W[1][leftid - 1];
C[leftid - 1] = max(leftsum, C[leftid - 1]);
leftid -= 1;
} else {
sum += take_right;
rollback.push_back({1, C[rightid + 1], take_right});
rightsum += W[1][rightid + 1];
C[rightid + 1] = max(rightsum, C[rightid + 1]);
rightid += 1;
}
now += 1;
}
// cerr << left << " = " << leftid << " " << rightid << "\n";
curr = 0;
for (int right = idx[X] + 1; right < N; ++right) {
curr += W[0][right];
ll add = max(0LL, curr - C[right]);
while (rollback.size() > 0 && sum + add > K) {
int p = rollback.back()[0];
ll pC = rollback.back()[1];
ll w = rollback.back()[2];
rollback.pop_back();
if (p == 0) {
C[leftid] = pC;
sum -= w;
if (ps[leftid] > C[leftid]) {
sum += ps[leftid] - C[leftid];
C[leftid] = ps[leftid];
}
leftid++;
} else {
sum -= w;
C[rightid] = pC;
if (ps[rightid] > C[rightid]) {
sum += ps[rightid] - C[rightid];
C[rightid] = ps[rightid];
}
rightid--;
}
now -= 1;
}
sum += add;
if (sum > K) continue;
C[right] += add;
ps[right] = curr;
now += 1;
res = max(res, now);
}
}
return res;
}
