#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
#define ff first
#define ss second
#define pii pair<int, int>
using ll = long long;
vector<bool> vis;
vector<ll> c;
vector<vector<pii>> E;
bool dfs(int x, int p = -1, ll sm = 0) {
bool tr = false;
if (vis[x]) {
tr = true;
c[x] = max(c[x], sm);
}
for (auto [i, w] : E[x]) {
if (i != p && dfs(i, x, sm + w)) {
tr = true;
c[x] = max(c[x], sm);
}
}
return tr;
}
int max_score(int n, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
E.assign(n, {});
for (int i = 0; i < n - 1; i++) {
E[U[i]].push_back({V[i], W[i]});
E[V[i]].push_back({U[i], W[i]});
}
auto f = [&](int st) -> vector<ll> {
queue<int> q;
vector<ll> dis(n, -1);
q.push(st); dis[st] = 0;
while (!q.empty()) {
auto x = q.front(); q.pop();
for (auto [i, w] : E[x]) {
if (dis[i] == -1) {
dis[i] = dis[x] + w;
q.push(i);
}
}
}
return dis;
};
vector<ll> disx = f(X), disy = f(Y);
vector<pii> u;
for (int i = 0; i < n; i++)
u.push_back({min(disx[i], disy[i]), i});
sort(u.begin(), u.end());
int mx = 0;
for (int mk = 0; mk < 1 << n; mk++) {
c.assign(n, -1);
vis.assign(n, false);
for (int i = 0; i < n; i++)
vis[i] = (mk >> i) & 1;
dfs(X); dfs(Y);
ll sm = 0;
int cnt = 0;
for (int i = 0; i < n && sm <= K; i++) {
if (c[i] != -1) {
sm += c[i];
cnt += 1 + (c[i] == max(disx[i], disy[i]));
}
}
if (sm > K) continue;
for (int i = 0; i < n; i++) {
if (c[u[i].ss] == -1) {
if ((sm += u[i].ff) > K) break;
cnt += 1 + (disx[u[i].ss] == disy[u[i].ss]);
}
}
mx = max(mx, cnt);
}
return mx;
}
