#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<vector<pii>> adj;
void dfs(int u, vector<ll> &dis, int p=-1, ll w=0) {
dis[u] = w;
for (auto [v, pe] : adj[u]) {
if (v==p) continue;
dfs(v, dis, u, w+pe);
}
}
bool cmp(pii a, pii b) {
if (a.first==b.first) {
return a.second > b.second;
}
else {
return a.first<b.first;
}
}
int max_score(int n, int x, int y, long long k,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
adj.assign(n, {});
vector<ll> disX(n, 0);
vector<ll> disY(n, 0);
for (int i=0; i<n-1; i++) {
int u = U[i];
int v = V[i];
int w = W[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(x, disX);
dfs(y, disY);
//Fijar [l, r] que me expando en X, expandir Y greedily
int res=0;
vector<pii> order(n);
for (int i=0; i<n; i++) {
order[i] = {disX[i], i};
}
int l=x, r=x;
sort(order.begin(), order.end(), cmp);
for (auto [val, i] : order) {
l = min(l, i);
r = max(r, i);
k -= val;
ll mx=k;
vector<bool> vis(n, false);
for (int i=l; i<=r; i++) {
vis[i] = true;
mx -= disX[i];
}
if (mx<0) continue;
vector<ll> cost(n, 0);
for (int i=0; i<n; i++) {
if (vis[i]) {
if (disX[i] >= disY[i]) {
cost[i] = 0;
}
else {
cost[i] = disY[i]-disX[i];
}
}
else {
cost[i] = disY[i];
}
}
int ans = r-l+1;
vector<ll> acc;
if (r>=y) {
//etsa contenido
for (int i=0; i<n; i++) {
acc.push_back(cost[i]);
}
sort(acc.begin(), acc.end());
ll P = mx;
for (auto v : acc) {
if (v<=P) {
P -= v;
ans++;
}
}
res = max(res, ans);
continue;
}
for (int i=r+1; i<n; i++) {
acc.push_back(disY[i]);
}
sort(acc.begin(), acc.end());
ll P = mx;
//Caso no solaparlos
for (auto v : acc) {
if (v<=P) {
P -= v;
ans++;
}
}
res = max(res, ans);
acc.clear();
for (int i=0; i<=r; i++) {
acc.push_back(cost[i]);
}
for (int i=y+1; i<n; i++) {
acc.push_back(cost[i]);
}
ans = (r-l+1);
//r+1...y
//cout << l << " " << r << " " << y << endl;
ans += (y-(r+1)+1);
sort(acc.begin(), acc.end());
P = mx;
for (int i=r+1; i<=y; i++) {
P -= disY[i];
}
if (P<0) continue;
for (auto v : acc) {
if (v<=P) {
P -= v;
ans++;
}
}
res = max(res, ans);
}
return res;
}
