#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<vector<ll>> dist(2, vector<ll>(N));
vector<int> path, current;
auto dfs = [&](auto& dfs, int v, int p, int i) -> void {
current.push_back(v);
if (v == Y && i == 0) {
path = current;
}
for (auto& [u, w] : adj[v]) {
if (u == p) continue;
dist[i][u] = dist[i][v] + w;
dfs(dfs, u, v, i);
}
current.pop_back();
};
dfs(dfs, X, -1, 0);
dfs(dfs, Y, -1, 1);
vector<array<ll, 2>> cost;
for (int i = 0; i < N; ++i) {
ll c1 = min(dist[0][i], dist[1][i]);
ll c2 = max(dist[0][i], dist[1][i]);
cost.push_back({c1, i});
cost.push_back({c2, i});
}
ll tot = 0;
int res = 0;
vector<bool> vis(N);
sort(begin(cost), end(cost));
for (int i = 0; i < (int)cost.size(); ++i) {
ll c = cost[i][0];
int j = cost[i][1];
if (vis[j]) {
c -= min(dist[0][j], dist[1][j]);
}
if (tot + c <= K) {
tot += c;
res += 1;
vis[j] = true;
} else {
break;
}
}
vector<bool> free(N);
// cout << "Path = ";
for (auto& u : path) {
// cout << u << " ";
free[u] = true;
}
// cout << "\n";
int m = 0;
while (m + 1 < (int)path.size() && dist[0][path[m + 1]] < dist[1][path[m + 1]]) m++;
vector<vector<ll>> DP(2);
auto merge = [&](vector<ll> a, vector<ll>& b) -> vector<ll> {
vector<ll> res(a.size() + b.size() - 1, K + 1);
for (int i = 0; i < (int)a.size(); ++i) {
for (int j = 0; j < (int)b.size(); ++j) {
res[i + j] = min(res[i + j], a[i] + b[j]);
}
}
return res;
};
auto solve = [&](auto& solve, int way, int v, int p) -> array<vector<ll>, 2> {
vector<vector<ll>> dp = {{0}, {0}};
for (auto [u, _] : adj[v]) {
if (u == p) continue;
array<vector<ll>, 2> now = solve(solve, way, u, v);
dp[0] = merge(dp[0], now[0]);
dp[1] = merge(dp[1], now[1]);
}
array<vector<ll>, 2> ndp;
ndp[0] = {0};
ndp[1] = {0};
ll opt1 = dist[way][v], opt2 = dist[way ^ 1][v];
assert(opt1 <= opt2);
int fr = 0;
if (free[v]) {
fr = 1;
opt2 -= opt1;
opt1 = 0;
}
for (int i = 0; i < dp[0].size(); ++i) {
int nxt = i + 1 - fr;
while (ndp[0].size() <= nxt) ndp[0].push_back(K + 1);
while (ndp[1].size() <= nxt) ndp[1].push_back(K + 1);
auto& _ndp0 = ndp[0][nxt];
_ndp0 = min(_ndp0, dp[0][i] + opt1);
_ndp0 = min(_ndp0, K + 1);
auto& _ndp = ndp[1][nxt];
_ndp = min(_ndp, dp[0][i] + opt1);
_ndp = min(_ndp, K + 1);
}
for (int i = 0; i < dp[1].size(); ++i) {
int nxt = i + 2 - fr;
while (ndp[1].size() <= nxt) ndp[1].push_back(K + 1);
auto& _ndp = ndp[1][nxt];
_ndp = min(_ndp, dp[1][i] + opt2);
_ndp = min(_ndp, K + 1);
}
return ndp;
};
// cout << "PATH = " << path[m] << " " << path[m + 1] << "\n";
DP[0] = solve(solve, 0, path[m], path[m + 1])[1];
DP[1] = solve(solve, 1, path[m + 1], path[m])[1];
ll add = 0;
for (auto& u : path) {
add += min(dist[0][u], dist[1][u]);
}
auto fin = merge(DP[0], DP[1]);
for (int i = 0; i < (int)fin.size(); ++i) {
// cerr << add << " + " << fin[i] << " = " << i + (int)path.size() << "\n";
if (add + fin[i] <= K) {
res = max(res, i + (int)path.size());
}
}
return res;
}
