#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";
auto calc = [&](int id, int right, ll sum, ll curr, vector<ll> C) -> int {
int now = 0;
bool ok = true;
for (;id <= right;) {
if (id >= N) {
assert(false);
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;
now += 1;
}
if (!ok) {
return -N;
}
// cerr << left << " " << right << " = ";
// for (int i = 0; i < N; ++i) {
// cerr << C[i] << " ";
// }
// cerr << "\n";
ll left_sum = 0, right_sum = 0;
id = idx[Y];
int leftid = id, rightid = id;
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;
sum += pick_left;
left_sum += W[1][leftid];
C[line[leftid]] += pick_left;
} else {
rightid += 1;
now += 1;
sum += pick_right;
right_sum += W[1][rightid];
C[line[rightid]] += pick_right;
}
}
// cout << left << " " << right << " = " << now << "\n";
// cout << "C = ";
// for (auto& u : C) {
// cout << u << " ";
// }
// cout << "\n";
return now;
};
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) break;
int l = idx[X], r = N - 2;
curr = 0;
id = idx[X];
while (l < r) {
int m = (l + r) / 2;
ll left = calc(id, m, sum, curr, C);
ll right = calc(id, m + 1, sum, curr, C);
if (left < 0) {
r = m - 1;
continue;
}
if (left >= right) {
r = m;
} else {
l = m + 1;
}
}
now += calc(id, r, sum, curr, C);
cerr << left << " = " << now << "\n";
res = max(res, now);
}
return res;
}
