#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
vector<vector<pair<int,int>>> G(N);
for (int 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<ll> dx(N, -1), dy(N, -1);
dx[X] = 0;
dy[Y] = 0;
queue<pair<int,int>> q;
q.push({X, 0});
q.push({Y, 1});
while (!q.empty()){
int cur = q.front().first, s = q.front().second;
q.pop();
for (pair<int,int> next : G[cur]){
if (s == 0 && dx[next.first] == -1){
dx[next.first] = dx[cur]+(ll)next.second;
q.push({next.first, s});
}
if (s == 1 && dy[next.first] == -1){
dy[next.first] = dy[cur]+(ll)next.second;
q.push({next.first, s});
}
}
}
ll res = 0;
vector<ll> c1(N), c2(N);
priority_queue<ll> pq1;
set<pair<ll,int>> pq2, pq3;
int ans2 = 0;
vector<int> lv(N, 0);
for (int i=0; i<N; i++){
c1[i] = min(dx[i], dy[i]);
c2[i] = max(dx[i], dy[i])-c1[i];
pq1.push(-c1[i]);
if (dx[i]+dy[i] == dx[Y]){
res += c1[i];
lv[i]++;
ans2++;
pq2.insert({c2[i], i});
}
else {
if (c2[i] > c1[i]) pq2.insert({c1[i], i});
else pq3.insert({c1[i]+c2[i], i});
}
}
int ans = 0;
ll rem = K;
while (!pq1.empty() && rem >= -pq1.top()){
rem += pq1.top();
pq1.pop();
ans++;
}
rem = K-res;
while (pq2.size() >= 2 && pq3.size() >= 1){
int opt1 = pq2.begin()->first + next(pq2.begin())->first, opt2 = pq3.begin()->first;
if (rem < min(opt1, opt2)) break;
if (opt1 < opt2){
rem -= pq2.begin()->first;
ans2++;
int i = pq2.begin()->second;
pq2.erase(pq2.begin());
if (lv[i] == 0) pq2.insert({c2[i], i});
lv[i]++;
}
else {
rem -= pq3.begin()->first;
ans2 += 2;
int i = pq3.begin()->second;
pq3.erase(pq3.begin());
lv[i] += 2;
}
}
while (!pq3.empty() && rem >= pq3.begin()->first){
rem -= pq3.begin()->first;
ans2 += 2;
int i = pq3.begin()->second;
pq3.erase(pq3.begin());
lv[i] += 2;
}
while (!pq2.empty() && rem >= pq2.begin()->first){
rem -= pq2.begin()->first;
ans2++;
int i = pq2.begin()->second;
pq2.erase(pq2.begin());
if (lv[i] == 0) pq2.insert({c2[i], i});
lv[i]++;
}
for (int i=0; i<N; i++){
if (lv[i] == 0 && rem >= c1[i]){
rem -= c1[i];
ans2++;
}
}
if (res <= K) ans = max(ans, ans2);
return ans;
}
