#include "closing.h"
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
using namespace std;
const int MAXN=200010;
vector<pair<int,int>> g[MAXN];
long long distX[MAXN], distY[MAXN];
int dd[MAXN];
vector<int> path;
long long dist=0;
void dfsx(int at, int p) {
for(auto [to,w]:g[at]) {
if(to==p)continue;
distX[to]=distX[at]+w;
dfsx(to, at);
}
}
void dfsy(int at, int p) {
for(auto [to,w]:g[at]) {
if(to==p)continue;
distY[to]=distY[at]+w;
dfsy(to, at);
if(dd[to])dist+=w;
dd[at]|=dd[to];
}
if(dd[at])path.push_back(at);
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
for(int i = 0;i<N-1;i++) {
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
dist=0;
dd[X]=1;
dfsx(X, -1);
dfsy(Y, -1);
int ans=0;
// case 1
{
int cnt=0;
priority_queue<long long> pq;
for(int i = 0;i<N;i++) {
pq.push(-distX[i]);
pq.push(-distY[i]);
}
long long sum=0;
while(sum<=K and pq.size()) {
sum-=pq.top();
cnt++;
pq.pop();
if(sum<=K)ans=max(ans,cnt);
}
}
// case 2
{
for(int i = 0;i<N;i++) {
if(distX[i]>distY[i])swap(distX[i], distY[i]);
distY[i]-=distX[i];
}
int upd[N];
memset(upd, 0, sizeof upd);
long long sum=0;
int cnt=0;
priority_queue<long long> pq1;
priority_queue<pair<long long,int>> pq2;
multiset<long long> ms;
for(int i:path) {
sum+=distX[i];
pq1.push(-distY[i]);
cnt++;
upd[i]++;
}
for(int i = 0;i<N;i++) {
if(upd[i])continue;
if(distX[i]>distY[i]) {
pq2.push({-(distY[i]+distX[i]), i});
ms.insert(distX[i]);
}
else {
pq1.push(-distX[i]);
pq1.push(-distY[i]);
}
}
if(sum<=K)ans=max(ans, cnt);
if(pq1.size() and sum-pq1.top()<=K)ans=max(ans, cnt+1);
if(ms.size() and sum+(*ms.begin())<=K)ans=max(ans, cnt+1);
if(pq1.size() and ms.size() and sum-pq1.top()+(*ms.begin())<=K)ans=max(ans, cnt+2);
while(pq1.size() or pq2.size()) {
if(pq1.size()>=2 and pq2.size()) {
long long tmp=pq1.top();
pq1.pop();
if(-tmp-pq1.top()>=-pq2.top().first) {
sum-=pq2.top().first;
ms.erase(ms.find(distX[pq2.top().second]));
cnt+=2;
pq2.pop();
pq1.push(tmp);
}
else {
sum-=tmp;
cnt++;
}
}
else if(pq1.size()<=1 and pq2.size()) {
sum-=pq2.top().first;
ms.erase(ms.find(distX[pq2.top().second]));
cnt+=2;
pq2.pop();
}
else if(pq2.size()==0 and pq1.size()) {
sum-=pq1.top();
pq1.pop();
cnt++;
}
if(sum<=K)ans=max(ans, cnt);
if(pq1.size() and sum-pq1.top()<=K)ans=max(ans, cnt+1);
if(ms.size() and sum+(*ms.begin())<=K)ans=max(ans, cnt+1);
if(pq1.size() and ms.size() and sum-pq1.top()+(*ms.begin())<=K)ans=max(ans, cnt+2);
}
}
for(int i = 0;i<=N;i++) {
dd[i]=0;
distX[i]=distY[i]=0;
g[i].clear();
}
path.clear();
return ans;
}
