#include"closing.h"
#include<bits/stdc++.h>
#include <cstdio>
using namespace std;
using ll = long long;
vector<vector<pair<ll, ll>>> v;
vector<ll> pref[2];
vector<ll> used[2];
vector<ll> cnt;
void dfs(ll x, ll p, ll k) {
for (auto [to, w] : v[x]) {
if (to == p)
continue;
pref[k][to] = pref[k][x] + w;
dfs(to, x, k);
}
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
ll res = 2;
v.resize(N);
cnt.resize(N);
for (ll i = 0; i < 2; i++) {
pref[i].resize(N);
used[i].resize(N);
fill(pref[i].begin(), pref[i].end(), 0);
fill(used[i].begin(), used[i].end(), 0);
}
fill(cnt.begin(), cnt.end(), 0);
for (ll i = 0; i < N - 1; i++) {
v[U[i]].push_back({V[i], W[i]});
v[V[i]].push_back({U[i], W[i]});
}
dfs(X, X, 0);
dfs(Y, Y, 1);
set<pair<ll, pair<ll, ll>>> s;
used[0][X] = 1;
used[1][Y] = 1;
cnt[X] = cnt[Y] = 1;
// cout << X << " " << Y << "\n";
// for (int i = 0; i < N; i++) {
// cout << i << " " << pref[0][i] << " " << pref[1][i] << "\n";
// }
for (auto [to, w] : v[X]) {
s.insert({pref[0][to], {to, 0}});
used[0][to] = 1;
}
for (auto [to, w] : v[Y]) {
s.insert({pref[1][to], {to, 1}});
used[1][to] = 1;
}
while (!s.empty()) {
auto it = *s.begin();
if (it.first > K)
break;
// cout << "add " << K << " " << it.first << " " << it.second.first << " " << it.second.second << "\n";
res++;
s.erase(s.begin());
K -= it.first;
if (cnt[it.second.first] == 0 && used[it.second.second ^ 1][it.second.first]) {
s.erase({pref[it.second.second ^ 1][it.second.first], {it.second.first, it.second.second ^ 1}});
s.insert({pref[it.second.second ^ 1][it.second.first] - it.first, {it.second.first, it.second.second ^ 1}});
// cout << "+ " << pref[it.second.second ^ 1][it.second.first] - it.first << " " << it.second.first << "\n";
}
cnt[it.second.first]++;
for (auto [to, w] : v[it.second.first]) {
if (used[it.second.second][to])
continue;
used[it.second.second][to] = 1;
if (cnt[to] == 0)
s.insert({pref[it.second.second][to], {to, it.second.second}});
else
s.insert({pref[it.second.second][to] - pref[it.second.second ^ 1][to], {to, it.second.second}});
}
}
// cout << "_____\n";
for (int i = 0; i < N; i++) {
v[i].clear();
}
cnt.clear();
for (ll i = 0; i < 2; i++) {
used[i].clear();
pref[i].clear();
}
return res;
}
