#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];
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) {
if (u != 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 takeX = 0; takeX < m; takeX++) {
for (int takeY = m - 1; takeY >= 0; takeY--) {
for (int i = 0; i < m; i++)
paid[i] = 0;
priority_queue<aaa> pq;
for (int i = 0; i <= takeX; i++) {
int v = path[i];
paid[i] = max(paid[i], distX[v]);
}
for (int i = m - 1; i >= takeY; i--) {
int v = path[i];
paid[i] = max(paid[i], distY[v]);
}
long long c = 0;
for (int i = 0; i < m; i++) {
c += paid[i];
int v = path[i];
if (paid[i] == distX[v] || paid[i] == distY[v]) {
for (int u: subtree[v])
pq.push({0, u, cost1[u]});
}
}
if (c > k)
continue;
int score = takeX + 1 + m - takeY;
while (!pq.empty() && c + pq.top().c <= k) {
auto p = pq.top();
pq.pop();
// printf("%d %d %lld\n", p.t, p.v, p.c);
score++;
c += p.c;
int v = p.v;
if (p.t == 0)
pq.push({1, v, upgrade[v]});
}
// printf("%d %d -> %d\n", takeX, takeY, score);
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;
}
