#include"closing.h"
#include<bits/stdc++.h>
// #include <cstdio>
using namespace std;
vector<vector<pair<int, int>>> v;
vector<int> pref[2];
vector<int> used[2];
vector<int> cnt;
void dfs(int x, int p, int 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) {
int res = 2;
if (X == Y)
res = 1;
v.resize(N);
cnt.resize(N);
for (int i = 0; i < 2; i++) {
pref[i].resize(N);
used[i].resize(N);
}
for (int 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<int, pair<int, int>>> s;
used[0][X] = 1;
used[1][Y] = 1;
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 << "\n";
res++;
s.erase(s.begin());
K -= it.first;
if (cnt[it.first] == 0) {
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}});
}
cnt[it.first]++;
for (auto [to, w] : v[it.second.first]) {
if (used[it.second.second][to])
continue;
s.insert({pref[it.second.second][to], {to, it.second.second}});
}
}
cnt.clear();
v.clear();
for (int i = 0; i < 2; i++) {
used[i].clear();
pref[i].clear();
}
return res;
}
