#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
void calc_dist(ll n, ll p, vector<ll> &dist, vector<vector<pll>> &g){
for(auto[i, d]: g[n]) if(i != p){
dist[i] = dist[n] + d;
calc_dist(i, n, dist, g);
}
}
ll max_without_overlap(vector<vector<ll>> &dist, ll n, ll k){
ll ans = 0, credit = k;
priority_queue<pll, vector<pll>, greater<pll>> pq;
for(ll i = 0; i < n; i++) pq.push({dist[0][i], i}), pq.push({dist[1][i], i});
vector<bool> vis(n);
while(pq.size()){
auto[d, node] = pq.top(); pq.pop();
if(vis[node]) continue;
vis[node] = 1;
if(credit - d < 0) continue;
credit -= d;
ans++;
}
return ans;
}
int max_score(int N, int X, int Y, long long k, vector<int> u, vector<int> v, vector<int> w)
{
ll n = N, x = X, y = Y;
vector<vector<pll>> g(n);
for(ll i = 0; i < n-1; i++) g[u[i]].push_back({v[i], w[i]}), g[v[i]].push_back({u[i], w[i]});
vector<vector<ll>> dist(2, vector<ll>(n)), pref(2, vector<ll>(n+1));
calc_dist(x, -1, dist[0], g);
calc_dist(y, -1, dist[1], g);
ll ans = max_without_overlap(dist, n, k);
for(ll i = 0; i < n; i++) for(ll j = i; j < n; j++) if(i <= x && y <= j) {
ll s = 0, cnt = j - i + 1;
priority_queue<ll, vector<ll>, greater<ll>> pq;
for(ll l = i; l <= j; l++) s += min(dist[0][l], dist[1][l]), pq.push(max(dist[0][l], dist[1][l]) - min(dist[0][l], dist[1][l]));
if(s > k) continue;
while(pq.size()){
ll d = pq.top(); pq.pop();
if(s + d > k) break;
s += d, cnt++;
}
ans = max(ans, cnt);
}
return ans;
}
