#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);
vi seen(maxn,0);
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;
seen[i]=0;
}
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<array<ll,3>> qa={{0,valb[x],x},{(ll)(2e18+1),0,-1}},qb={{0,vala[y],y},{(ll)(2e18+1),0,-1}};
int ans=0;
while (min((*qa.begin())[0],(*qb.begin())[0])<=k) {
ans++;
if ((*qa.begin())[0]<(*qb.begin())[0] || ((*qa.begin())[0]==(*qb.begin())[0] && (*qa.begin())[1]<=(*qb.begin())[1])) {
auto temp=*qa.begin();
ll val=temp[0],_=temp[1],cur=temp[2];
seen[cur]=1;
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],(seen[to]?(ll)(2e18+1):valb[to]),to});
}
}
if (qb.count({valb[cur],vala[cur],cur})) {
qb.erase({valb[cur],vala[cur],cur});
qb.insert({valb[cur]-val_cur[cur],(ll)(2e18+1),cur});
}
}
else {
auto temp=*qb.begin();
ll val=temp[0],_=temp[1],cur=temp[2];
seen[cur]=1;
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],(seen[to]?(ll)(2e18+1):vala[to]),to});
}
}
if (qa.count({vala[cur],valb[cur],cur})) {
qa.erase({vala[cur],valb[cur],cur});
qa.insert({vala[cur]-val_cur[cur],(ll)(2e18+1),cur});
}
}
}
return ans;
}
