#include "closing.h"
#include <bits/stdc++.h>
#include <vector>
using ll = long long;
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<array<ll, 2>>> 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]});
}
int sol =0;
//tre casi
//primo caso: no intersezioni
int sol1 = 0;
vector<ll> dst(n, 1e18);
function<void(int, int)> find_dst = [&](int v, int p){
for(auto [u, w]: adj[v]){
if(u==p) continue;
dst[u] = min(dst[u], dst[v]+w);
find_dst(u, v);
}
return;
};
dst[x] = 0;
find_dst(x, -1);
ll l = dst[y];
dst[y] = 0;
find_dst(y, -1);
vector<ll> dst_ = dst;
sort(dst_.begin(), dst_.end());
ll k_ = k;
for(ll i: dst_){
if(k_-i >=0){
k_-=i;
sol1++;
}
else break;
}
sol = sol1;
//secondo caso: intersezione solo nel path
sol1 = 0;
vector<ll> dst2;
k_ = k;
for(int i =0; i<x; i++) dst2.push_back(dst[i]);
for(int i = y+1; i<n; i++) dst2.push_back(dst[i]);
for(int i = x; i<=y; i++){
k_-= dst[i];
sol1++;
}
if(k_ < 0) return sol;
for(int i = x; i<=y; i++){
dst2.push_back(l-2*dst[i]);
assert(l-2*dst[i] >= 0);
}
sort(dst2.begin(), dst2.end());
for(ll i: dst2){
if(k_ - i >= 0){
k_ -= i;
sol1++;
}
else break;
}
sol =max(sol, sol1);
//terzo caso: le intersezioni strabordano
sol1 = 0;
k_ = k;
for(int i = x; i<=y; i++){
k_ -= max(dst[i], l-dst[i]);
sol1 += 2;
}
if(k_ < 0) return sol;
sol = max(sol1, sol);
vector<int> dst3;
for(int i=0; i<x; i++) dst3.push_back(dst[i]);
for(int i=y+1; i<n; i++) dst3.push_back(dst[i]);
sort(dst3.begin(), dst3.end());
for(int i = 0; i<dst3.size(); i++){
k_ -= dst3[i];
sol1++;
if(k_<0) return sol;
ll k__ = k_;
int sol1_ = sol1;
for(int j = 0; j<=i; j++){
if(k__-l>=0){
k__-=l;
sol1_++;
}
else break;
}
sol = max(sol, sol1_);
}
return sol;
}
