#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 {
if (x.c == c)
return x.t < t;
return x.c < c;
}
};
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];
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 v = 0; v < n; v++)
level[v] = 0;
long long c = 0;
int score = 0;
priority_queue<aaa> pq1, pq2;
for (int v = 0; v < n; v++) {
if (onPath[v] && takeAll) {
c += cost1[v];
level[v] = 1;
pq1.push({1, v, upgrade[v]});
score++;
} else {
if (takeAll) {
if (upgrade[v] >= cost1[v])
pq1.push({0, v, cost1[v]});
else
pq2.push({0, v, cost1[v] + upgrade[v]});
} else
pq1.push({0, v, cost1[v]});
}
}
if (c > k)
continue;
bool done = false;
while (!pq1.empty() && !pq2.empty() && !done) {
auto p1 = pq1.top();
pq1.pop();
auto p2 = pq2.top();
pq2.pop();
if (level[p1.v] > p1.t) {
pq2.push(p2);
continue;
}
if (level[p2.v] > p2.t) {
pq1.push(p1);
continue;
}
long long c11 = INF;
while (!pq1.empty() && level[pq1.top().v] != pq1.top().t)
pq1.pop();
if (!pq1.empty())
c11 = p1.c + pq1.top().c;
long long c22 = p2.c;
// printf("COMPAR %lld %lld\n", c11, c22);
done = true;
if (c11 < c22) {
// auto p11 = pq1.top();
// pq1.pop();
if (c + c11 <= k) {
done = false;
// c += c11;
c += p1.c;
// score += 2;
score++;
level[p1.v]++;
// level[p11.v]++;
// printf("DIN PQ1 %d %d\n", p1.v, p11.v);
if (takeAll) {
if (p1.t == 0)
pq1.push({1, p1.v, upgrade[p1.v]});
// if (p11.t == 0)
// pq1.push({1, p11.v, upgrade[p11.v]});
}
} else {
pq1.push(p1);
// pq1.push(p11);
}
pq2.push(p2);
} else {
if (c + c22 <= k) {
// printf("DIN PQ2 %d\n", p1.v);
done = false;
c += c22;
score += 2;
level[p2.v] = 2;
} else
pq2.push(p2);
pq1.push(p1);
}
// printf("%lld\n", c);
}
while (!pq1.empty()) {
auto p1 = pq1.top();
pq1.pop();
if (level[p1.v] > p1.t)
continue;
if (c + p1.c <= k) {
c += p1.c;
score++;
level[p1.v]++;
if (takeAll && p1.t == 0)
pq1.push({1, p1.v, upgrade[p1.v]});
}
// printf("%lld\n", c);
}
while (!pq2.empty()) {
auto p2 = pq2.top();
pq2.pop();
if (level[p2.v] > 0)
continue;
if (c + p2.c <= k) {
c += p2.c;
score += 2;
level[p2.v] = 2;
}
// printf("%lld\n", c);
}
// printf("%d %d\n", takeAll, 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;
}
