#include "closing.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int max_score(int n, int x, int y, long long k, vector<int> U, vector<int> V, 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<i64>> dis(n, vector<i64>(2, 0));
vector<vector<int>> next(n, vector<int>(2, -1));
function<void(int, int, int)> dfs = [&](int u, int p, int t) {
for (auto [v, w] : adj[u]) {
if (v == p) continue;
dis[v][t] = dis[u][t] + w;
next[v][!t] = u;
dfs(v, u, t);
}
};
dfs(x, -1, 0);
dfs(y, -1, 1);
i64 pathCost = 0;
vector<int> path, onPath(n, 0);
int z = x;
while (true) {
path.push_back(z);
onPath[z] = 1;
pathCost += min(dis[z][0], dis[z][1]);
if (z == y) {
break;
}
z = next[z][0];
}
vector<pair<i64, int>> vec;
vector<i64> one(n), two(n);
for (int u = 0; u < n; ++u) {
one[u] = min(dis[u][0], dis[u][1]);
two[u] = max(dis[u][0], dis[u][1]);
vec.push_back({two[u], u});
}
sort(vec.begin(), vec.end(), greater<pair<i64, int>>());
vector<int> used(n, 0);
auto work = [&](bool mark, i64 k) {
int ret = 0;
vector<int> vis = used;
if (mark) {
for (auto u : path) {
if (vis[u] == 0) {
vis[u] = 1;
k -= one[u];
++ret;
}
}
} else {
vis[x] = vis[y] = 1;
ret = 2;
}
if (k < 0) {
return (int)-1e9;
}
priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;
for (int u = 0; u < n; ++u) {
bool found = 0;
for (auto [v, w] : adj[u]) {
found |= vis[v];
}
if (found) {
pq.push({one[u], u});
}
}
while (pq.size()) {
auto [cost, u] = pq.top();
pq.pop();
if (cost > k) {
break;
}
if (vis[u]) {
continue;
}
vis[u] = 1;
k -= cost;
++ret;
for (auto [v, w] : adj[u]) {
pq.push({one[v], v});
}
}
return ret;
};
auto canMark = [&](int u, i64 k, i64 pathCost) {
pathCost -= (onPath[u] ? one[u] : 0);
k -= two[u];
return k >= pathCost;
};
int ans = 0;
if (n <= 20) {
for (int mask = 0; mask < (1 << n); ++mask) {
fill(used.begin(), used.end(), 0);
i64 curK = k;
for (int j = 0; j < n; ++j) {
if (mask & (1 << j)) {
used[j] = 1;
curK -= two[j];
}
}
int cnt = __builtin_popcount(mask);
ans = max(ans, work(cnt > 0, curK) + 2 * cnt);
}
} else {
for (int c = 0; c <= n; ++c) {
if (c) {
ans = max(ans, work(1, k) + 2 * c);
} else {
ans = max(ans, work(0, k));
}
while (vec.size() && canMark(vec.back().second, k, pathCost) == 0) {
vec.pop_back();
}
if (vec.size() == 0) {
break;
}
auto [cost, u] = vec.back();
vec.pop_back();
used[u] = 1;
pathCost -= (onPath[u] ? one[u] : 0);
k -= two[u];
}
}
return ans;
}
