#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);
int now = left + 1;
int id = idx[X];
bool ok = true;
for (int it = 0; it <= left; ++it) {
if (id < 0) {
ok = false;
break;
}
int j = line[id];
curr += W[0][id];
if (sum + curr - C[j] > K) {
ok = false;
break;
}
sum += curr - C[j];
C[j] = curr;
id -= 1;
}
if (!ok) continue;
ll left_sum = 0, right_sum = 0;
id = idx[Y];
now += 1;
int leftid = id, rightid = id;
vector<array<ll, 3>> op;
while (true) {
ll pick_left = K, pick_right = K;
if (leftid - 1 >= 0) {
int j = line[leftid - 1];
pick_left = max(0LL, left_sum + W[1][leftid - 1] - C[j]);
}
if (rightid + 1 < N) {
int j = line[rightid + 1];
pick_right = max(0LL, right_sum + W[1][rightid + 1] - C[j]);
}
if (min(pick_left, pick_right) + sum > K) {
break;
}
if (pick_left < pick_right) {
leftid -= 1;
now += 1;
op.push_back({0, pick_left, C[line[leftid]]});
sum += pick_left;
left_sum += W[1][leftid];
C[line[leftid]] += pick_left;
} else {
rightid += 1;
now += 1;
sum += pick_right;
op.push_back({1, pick_right, C[line[rightid]]});
right_sum += W[1][rightid];
C[line[rightid]] += pick_right;
}
}
curr = 0;
for (int right = idx[X]; right < N; ++right) {
id = right;
int j = line[id];
curr += W[0][id];
while (sum + curr - C[j] > K && (int)op.size()) {
auto [p, w, _C] = op.back();
op.pop_back();
if (p == 0) {
sum -= w;
C[line[leftid]] = _C;
leftid++;
} else {
sum -= w;
C[line[rightid]] = _C;
rightid--;
}
now -= 1;
}
if (sum + max(0LL, curr - C[j]) > K) {
break;
}
if (curr > C[j]) {
sum += curr - C[j];
C[j] = curr;
}
res = max(res, now);
now += 1;
}
}
return res;
}
