#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vector<vector<pair<int, long long>>> 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]});
}
function<void(int, int, vector<long long> &)> dfs = [&](int a, int p, vector<long long> &d) {
for (auto x : adj[a]) {
if (x.first == p) continue;
d[x.first] = d[a]+x.second;
dfs(x.first, a, d);
}
};
vector<long long> dx(N, 0), dy(N, 0);
dfs(X, -1, dx); dfs(Y, -1, dy);
int best = 0;
long long sum = 0;
vector<pair<long long, int>> massi, mini;
for (int i = 0; i < N; i++) {
massi.push_back({max(dx[i], dy[i]), i});
mini.push_back({min(dx[i], dy[i]), i});
}
sort(massi.begin(), massi.end());
sort(mini.begin(), mini.end());
// senza doppi
for (auto x : mini) {
sum += x.first;
if (sum <= K) best++;
}
sum = 0;
vector<int> tkx(N, 0), tky(N, 0);
for (int pref = 0; pref < N; pref++) {
int tot = 2*(pref+1);
sum += massi[pref].first;
int a = massi[pref].second;
if (tkx[a]) sum -= dx[a];
else if (tky[a]) sum -= dy[a];
tkx[a] = 1; tky[a] = 1;
// aggiorno i path
while (a != X) {
for (auto x : adj[a]) {
if (dx[a] <= dx[x.first]) continue;
a = x.first;
if (tkx[a]) continue;
tkx[a] = 1;
sum += dx[a];
tot++;
break;
}
}
a = massi[pref].second;
while (a != Y){
for (auto x : adj[a]) {
if (dy[a] <= dy[x.first]) continue;
a = x.first;
if (tky[a]) continue;
tky[a] = 1;
sum += dy[a];
tot++;
break;
}
}
if (sum > K) break;
long long currsum = sum;
// aggiungo i minimi
for (int i = 0; i < N; i++) {
int h = mini[i].second;
if (tkx[h] || tky[h]) continue;
currsum += mini[i].first;
if (currsum > K) break;
tot++;
}
best = max(tot, best);
}
return best;
}
