#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 2e18;
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
ll ans = 0;
vector<pii> adj[N];
vector<pii> fadj[N];
pii radj[N];
ll ht[N];
ll dx[N]; //distance x
for (ll i=0;i<(N-1);i++) {
adj[U[i]].push_back({V[i],W[i]});
adj[V[i]].push_back({U[i],W[i]});
}
ht[X]=0;
dx[X]=0;
radj[X]={-1,-1};
queue<ll> q0;
q0.push(X);
while (!q0.empty()) {
ll z = q0.front(); q0.pop();
for (pii p0: adj[z]) {
if (radj[z].first==p0.first) {
continue;
}
fadj[z].push_back(p0);
ht[p0.first]=ht[z]+1;
radj[p0.first]={z,p0.second};
dx[p0.first]=dx[z]+p0.second;
q0.push(p0.first);
}
}
ll D = ht[Y];
ll stpt[D+1];
stpt[D]=Y;
for (ll d=(D-1);d>=0;d--) {
stpt[d]=radj[stpt[d+1]].first;
}
ll dy[N];
dy[Y]=0;
queue<pii> q1; //point, search parent
q1.push({Y,-1});
while (!q1.empty()) {
pii pc = q1.front(); q1.pop();
for (pii p1: adj[pc.first]) {
if (p1.first==pc.second) {
continue;
}
dy[p1.first]=dy[pc.first]+p1.second;
q1.push({p1.first,pc.first});
}
}
pii dc[N];
for (ll i=0;i<N;i++) {
dc[i]={min(dy[i],dx[i]),max(dy[i],dx[i])-min(dy[i],dx[i])};
}
set<pii> s0; //{value, x}
vector<bool> found0(N,0);
ll val0 = K;
ll num0 = 0;
s0.insert({0,X});
s0.insert({0,Y});
while (!s0.empty()) {
pii p0 = *s0.begin(); s0.erase(s0.begin());
//cout << "p0: "<<p0.first<<", "<<p0.second<<"\n";
ll z = p0.second;
if (found0[z]) {
continue;
}
if (val0<p0.first) {
break;
}
val0 -= p0.first;
//cout << "new val0="<<val0<<"\n";
num0++;
found0[z]=1;
for (pii p1: adj[z]) {
if (!found0[p1.first]) {
s0.insert({dc[p1.first].first,p1.first});
}
}
}
ans = max(ans,num0);
set<pii> s1; //"individual hit" on point
set<pii> s2; //"double hit" on point
vector<bool> found1(N,0);
vector<bool> found2(N,0);
ll num1 = 0;
ll val1 = 0;
for (ll d=0;d<=D;d++) {
num1++;
val1 += dc[stpt[d]].first;
s1.insert({dc[stpt[d]].second,stpt[d]});
found1[stpt[d]]=1;
for (pii p0: fadj[stpt[d]]) {
if (d<D && p0.first==stpt[d+1]) {
continue;
}
s1.insert({dc[p0.first].first,p0.first});
s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
}
}
if (val1>K) {
return ans;
}
val1 = K-val1;
ll smax = -INF; //solo maximum
while (!s1.empty() && !s2.empty()) {
//"fix" both
while (!s2.empty()) {
ll z = (*s2.begin()).second;
if (found1[z]) {
s2.erase(s2.begin());
} else {
break;
}
}
while (!s1.empty()) {
pii pt = (*s1.begin());
ll z = pt.second; ll cval = pt.first;
if (found2[z]) {
s1.erase(s1.begin());
} else if (found1[z]) {
if (cval != dc[z].second) {
s1.erase(s1.begin());
} else {
break;
}
} else {
if (cval != dc[z].first) {
s1.erase(s1.begin());
} else {
break;
}
}
}
if (s1.empty() && s2.empty()) {
break;
} else if (s2.empty()) {
pii pt = *s1.begin(); s1.erase(s1.begin());
ll z = pt.second; ll cval = pt.first;
if (cval>val1) {
break;
}
num1++;
val1-=cval;
smax = max(smax,cval);
if (found1[z]) {
found2[z]=1;
for (pii p0: adj[z]) {
s1.insert({dc[p0.first].first,p0.first});
s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
}
} else {
found1[z]=1;
s1.insert({dc[z].second,z});
for (pii p0: adj[z]) {
s1.insert({dc[p0.first].first,p0.first});
s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
}
}
} else {
assert(!s1.empty() && !s2.empty());
//s1 empty, s2 nonempty impossible
pii p1 = *s1.begin(); pii p2 = *s2.begin();
if ((2*p1.first)<=p2.first) { //p1 "better"
ll z = p1.second; ll cval = p1.first;
s1.erase(s1.begin());
if (cval>val1) {
break;
}
num1++;
val1-=cval;
smax = min(smax,cval);
if (found1[z]) {
found2[z]=1;
for (pii p0: adj[z]) {
s1.insert({dc[p0.first].first,p0.first});
s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
}
} else {
found1[z]=1;
s1.insert({dc[z].second,z});
for (pii p0: adj[z]) {
s1.insert({dc[p0.first].first,p0.first});
s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
}
}
} else {
ll z = p1.second; ll cval = p1.first;
s2.erase(s2.begin());
if (cval>val1) {
ans = max(num1,ans);
if (p1.first<=val1) {
ans = max(num1+1,ans);
}
smax = max(smax,dc[z].second);
val1 -= cval;
if ((val1+smax)>=0) {
ans = max(num1+1,ans);
}
break;
}
num1 += 2;
val1 -= cval;
smax = max(smax,dc[z].second);
found1[z]=1;
found2[z]=1;
for (pii p0: adj[z]) {
s1.insert({dc[p0.first].first,p0.first});
s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
}
}
}
}
ans = max(num1,ans);
return ans;
}
