#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);
void dfs(int cur, int prev=-1, ll dist=0) {
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]=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);
dfs(x);
set<pl> q={{2e18+1,-1}};
for (int i=0; i<n; i++) {
q.insert({min(vala[i],valb[i]),i});
}
int ans1=0;
ll kk=0;
while (kk+q.begin()->fi<=k) {
auto [val,_]=*q.begin();
q.erase(q.begin());
kk+=val;
ans1++;
}
int ans=0;
multiset<pl> q_a={{2e18+1,-1},{2e18+1,-1}},q_b={{2e18+1,-1}},q_c={{2e18+1,-1}};
for (int i=0; i<n; i++) {
if (vala[i]+valb[i]==vala[y]) {
k-=min(vala[i],valb[i]);
ans++;
q_a.insert({max(vala[i],valb[i])-min(vala[i],valb[i]),i});
}
else if (min(vala[i],valb[i])<=max(vala[i],valb[i])-min(vala[i],valb[i])) {
q_a.insert({min(vala[i],valb[i]),i});
q_a.insert({max(vala[i],valb[i])-min(vala[i],valb[i]),i});
}
else {
q_b.insert({max(vala[i],valb[i]),i});
q_c.insert({min(vala[i],valb[i]),i});
}
}
if (k<0) {
ans=-1e9;
}
while (1) {
ll cst=min(q_b.begin()->fi,q_a.begin()->fi);
if (cst>k) {
break;
}
if (q_b.begin()->fi<=q_a.begin()->fi+next(q_a.begin())->fi) {
ans+=2;
auto [val,cur]=*q_b.begin();
k-=val;
if (k<0) {
k+=val;
ans-=2;
break;
}
q_c.erase({min(vala[cur],valb[cur]),cur});
q_b.erase(q_b.begin());
}
else {
k-=q_a.begin()->fi;
ans++;
q_a.erase(q_a.begin());
}
}
while (min(q_c.begin()->fi,q_a.begin()->fi)<=k) {
k-=min(q_c.begin()->fi,q_a.begin()->fi);
if (min(q_c.begin()->fi,q_a.begin()->fi)==q_c.begin()->fi) {
q_c.erase(q_c.begin());
}
else {
q_a.erase(q_a.begin());
}
ans++;
}
return max(ans,ans1);
}
