#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 <= x; i++) {
multiset<ll, greater<ll>> ms;
ll s = 0, cnt = 0;
for(ll j = i; j < y; j++){
cnt++;
s += min(dist[0][j], dist[1][j]);
s += max(dist[0][j], dist[1][j]) - min(dist[0][j], dist[1][j]);
cnt++;
ms.insert(max(dist[0][j], dist[1][j]) - min(dist[0][j], dist[1][j]));
while(ms.size()){
if(s <= k) break;
ll d = *ms.begin(); ms.erase(ms.begin());
s -= d; cnt--;
}
if(s > k) break;
}
for(ll j = y; s <= k && j < n; j++) {
cnt++;
s += min(dist[0][j], dist[1][j]);
s += max(dist[0][j], dist[1][j]) - min(dist[0][j], dist[1][j]);
cnt++;
ms.insert(max(dist[0][j], dist[1][j]) - min(dist[0][j], dist[1][j]));
while(ms.size()){
if(s <= k) break;
ll d = *ms.begin(); ms.erase(ms.begin());
s -= d; cnt--;
}
if(s > k) break;
ans = max(ans, cnt);
}
}
return ans;
}
