#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
const int maxn=2e5+10;
vector<vector<pi>> graph(maxn);
vl vala(maxn,0);
vl valb(maxn,0);
vl val_cur(maxn,0);
vi prev_a(maxn,-1);
vi prev_b(maxn,-1);
void dfs(int cur, int prev=-1, ll dist=0) {
prev_a[cur]=prev;
vala[cur]=dist;
for (auto [to,add]:graph[cur]) {
if (to!=prev) {
dfs(to,cur,dist+add);
}
}
}
int max_score(int n, int x, int y, long long k, vi u, vi v, vi w) {
for (int i=0; i<n; i++) {
graph[i].clear();
vala[i]=valb[i]=val_cur[i]=0;
prev_a[i]=prev_b[i]=-1;
}
for (int i=0; i<n-1; i++) {
graph[u[i]].pb({v[i],w[i]});
graph[v[i]].pb({u[i],w[i]});
}
dfs(y);
swap(vala,valb);
swap(prev_a,prev_b);
dfs(x);
set<pl> qa={{0,x},{2e18,-1}},qb={{0,y},{2e18,-1}};
int ans=0;
while (min(qa.begin()->fi,qb.begin()->fi)<=k) {
ans++;
if (qa.begin()->fi<=qb.begin()->fi) {
auto [val,cur]=*qa.begin();
qa.erase(qa.begin());
val_cur[cur]+=val;
k-=val;
for (auto [to,add]:graph[cur]) {
if (to!=prev_a[cur]) {
qa.insert({vala[to]-val_cur[to],to});
}
}
if (qb.count({valb[cur],cur})) {
qb.erase({valb[cur],cur});
qb.insert({valb[cur]-val_cur[cur],cur});
}
}
else {
auto [val,cur]=*qb.begin();
qb.erase(qb.begin());
val_cur[cur]+=val;
k-=val;
for (auto [to,add]:graph[cur]) {
if (to!=prev_b[cur]) {
qb.insert({valb[to]-val_cur[to],to});
}
}
if (qa.count({vala[cur],cur})) {
qa.erase({vala[cur],cur});
qa.insert({vala[cur]-val_cur[cur],cur});
}
}
}
return ans;
}
