#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 itleft = 0; itleft < N; ++itleft) {
ll sum = 0;
ll curr = 0;
vector<ll> C(N), ps(N);
int now = itleft + 1;
int id = idx[X];
bool ok = true;
for (int it = 0; it <= itleft; ++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;
}
int left = 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;
auto upd = [&]() -> void {
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;
leftsum += W[1][leftid - 1];
C[leftid - 1] = max(leftsum, C[leftid - 1]);
leftid -= 1;
} else {
sum += take_right;
rightsum += W[1][rightid + 1];
C[rightid + 1] = max(rightsum, C[rightid + 1]);
rightid += 1;
}
}
};
upd();
res = max(res, itleft + 1 + rightid - leftid + 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]);
sum += add;
while (sum > K) {
ll take_left = 0, take_right = 0;
if (leftid + 1 <= idx[Y]) {
take_left = max(0LL, leftsum - ps[leftid]);
}
if (rightid - 1 >= idx[Y]) {
take_right = max(0LL, rightsum - ps[rightid]);
}
if (max(take_left, take_right) == 0) break;
// cout << take_left << " = " << leftsum << " " << ps[leftid] << "\n";
// cout << take_right << " = " << rightsum << " " << ps[rightid] << "\n";
if (take_left > take_right) {
sum -= take_left;
C[leftid] = ps[leftid];
leftsum -= W[1][leftid];
leftid += 1;
} else {
sum -= take_right;
C[rightid] = ps[rightid];
rightsum -= W[1][rightid];
rightid -= 1;
}
now -= 1;
}
if (sum > K) continue;
upd();
C[right] += add;
ps[right] = curr;
// cout << left << " " << right << ":\n";
// for (int i = 0; i < N; ++i) {
// cout << ps[i] << " ";
// }
// cout << "\n";
// for (int i = 0; i < N; ++i) {
// cout << C[i] << " ";
// }
// cout << "\n\n";
now += 1;
// cerr << left << " " << right << " " << leftid << " " << rightid << " = " << now << "\n";
res = max(res, right - itleft + 1 + rightid - leftid + 1);
}
}
return res;
}
