#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
struct edge {
int u, v, c;
int other(int x) {
return u ^ v ^ x;
}
};
struct aaa {
int t, v;
long long c;
bool operator < (const aaa &x) const {
return x.c < c;
}
};
const int MAX_N = 2e5;
edge edges[MAX_N];
vector<int> adj[MAX_N];
int parent[MAX_N];
vector<int> path;
vector<int> subtree[MAX_N];
bool onPath[MAX_N];
int level[MAX_N];
long long dp[2 * MAX_N + 1];
long long distX[MAX_N], distY[MAX_N];
long long cost1[MAX_N], upgrade[MAX_N];
long long paid[MAX_N];
void calcDist(int u, int p, long long dist[]) {
// printf("aa %d %d %lld\n", u, p, dist[u]);
parent[u] = p;
for (int e: adj[u]) {
int v = edges[e].other(u), c = edges[e].c;
if (v == p)
continue;
dist[v] = dist[u] + c;
calcDist(v, u, dist);
}
}
void findSubtree(int u, int p, int w) {
subtree[w].push_back(u);
for (int e: adj[u]) {
int v = edges[e].other(u);
if (v == p || onPath[v])
continue;
findSubtree(v, u, w);
}
}
int max_score(int n, int x, int y, long long k,
vector<int> U, vector<int> V, vector<int> W) {
for (int v = 0; v < n; v++) {
adj[v].clear();
subtree[v].clear();
parent[v] = 0;
distX[v] = distY[v] = 0;
onPath[v] = false;
path.clear();
}
for (int e = 0; e < n - 1; e++) {
adj[U[e]].push_back(e);
adj[V[e]].push_back(e);
edges[e] = {U[e], V[e], W[e]};
}
calcDist(x, -1, distX);
calcDist(y, -1, distY);
int v = x;
while (v != y) {
path.push_back(v);
onPath[v] = true;
v = parent[v];
}
path.push_back(y);
onPath[y] = true;
int m = path.size();
for (int v = 0; v < n; v++) {
cost1[v] = min(distX[v], distY[v]);
upgrade[v] = max(distX[v], distY[v]) - cost1[v];
}
for (int i = 0; i < m; i++)
findSubtree(path[i], -1, path[i]);
// for (int v = 0; v < n; v++)
// printf("%d %lld %lld\n", v, distX[v], distY[v]);
// for (int v = 0; v < n; v++)
// printf("%d %lld %lld\n", v, cost1[v], upgrade[v]);
int maxScore = 0;
for (int takeAll = 0; takeAll < 2; takeAll++) {
for (int s = 2 * n; s >= 1; s--)
dp[s] = 1e18;
dp[0] = 0;
long long c = 0;
int s = 0;
for (int v = 0; v < n; v++) {
if (onPath[v] && takeAll) {
c += cost1[v];
s++;
}
for (int s = 2 * n; s >= 0; s--) {
if (onPath[v] && takeAll) {
if (s >= 1)
dp[s] = min(dp[s], dp[s - 1] + upgrade[v]);
}
else {
if (s >= 1)
dp[s] = min(dp[s], dp[s - 1] + cost1[v]);
if (takeAll && s >= 2)
dp[s] = min(dp[s], dp[s - 2] + cost1[v] + upgrade[v]);
}
}
// for (int s = 0; s <= 2 * n; s++)
// printf("%lld ", dp[s]);
// printf("\n");
}
if (c > k)
continue;
int score = 0;
// printf("%lld %d\n", c, s);
while (score + 1 <= 2 * n && dp[score + 1] <= k - c)
score++;
score += s;
maxScore = max(maxScore, score);
}
for (int v = 0; v < n; v++) {
adj[v].clear();
subtree[v].clear();
parent[v] = 0;
distX[v] = distY[v] = 0;
onPath[v] = false;
path.clear();
}
return maxScore;
}
