#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;
}
};
struct aa {
long long c;
int v;
};
const int MAX_N = 2e5;
const long long INF = 1e18;
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], used[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];
vector<aa> orderedByCost1, orderedByCost2;
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 i = 0; i < n; i++)
orderedByCost1.push_back({cost1[i], i});
sort(orderedByCost1.begin(), orderedByCost1.end(), [](aa x, aa y) {return x.c < y.c;});
int maxScore = 0;
long long c = 0;
while (maxScore < (int)orderedByCost1.size() && c + orderedByCost1[maxScore].c <= k) {
c += orderedByCost1[maxScore].c;
maxScore++;
}
long long cc = 0;
for (int v = 0; v < n; v++) {
if (onPath[v]) {
orderedByCost1.push_back({upgrade[v], v});
cc += cost1[v];
} else
orderedByCost2.push_back({cost1[v] + upgrade[v], v});
}
sort(orderedByCost1.begin(), orderedByCost1.end(), [](aa x, aa y) {return x.c < y.c;});
sort(orderedByCost2.begin(), orderedByCost2.end(), [](aa x, aa y) {return x.c < y.c;});
for (int t = 0; t < (int)orderedByCost2.size(); t++) {
used[orderedByCost2[t].v] = true;
cc += orderedByCost2[t].c;
if (cc > k)
continue;
long long c = cc;
int score = path.size() + t + 1;
for (int o = 0; o < (int)orderedByCost1.size(); o++) {
if (used[orderedByCost1[o].v])
continue;
if (c + orderedByCost1[o].c <= k) {
c += orderedByCost1[o].c;
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] = used[v] = false;
path.clear();
orderedByCost1.clear();
orderedByCost2.clear();
}
return maxScore;
}
