#include "closing.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
void dfs(int st, vector<array<int,2>>g[], int p, long long dist[], long long d){
dist[st]=d;
for(array<int,2>e:g[st]){
if(e[0]==p)
continue;
dfs(e[0],g,st,dist,d+e[1]);
}
}
int max_score(int n, int x, int y, long long k, vector<int> u, vector<int> v, vector<int> w) {
assert(x<y);
vector<array<int,2>>g[n];
int m = u.size();
for(int i = 0;i<m;i++){
g[u[i]].push_back({v[i],w[i]});
g[v[i]].push_back({u[i],w[i]});
}
long long distx[n], disty[n];
dfs(x,g,-1,distx,0);
dfs(y,g,-1,disty,0);
long long cost1[n],cost2[n];
for(int i = 0;i<n;i++){
cost1[i]=min(distx[i],disty[i]);
cost2[i]=max(distx[i],disty[i])-cost1[i];
}
int ans1 = 0;
//only till level 1.
priority_queue<long long,vector<long long>,greater<long long>>pq;
for(int i = 0;i<n;i++){
pq.push(cost1[i]);
}
long long curk = 0;
while(curk<=k){
long long a = pq.top();
pq.pop();
if(curk+a>k)
break;
ans1++;
curk+=a;
}
curk=0;
int ans2 = 0;
//now both levels, after doing all in between.
bool vis[n];
fill(vis,vis+n,0);
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq2;
for(int i = 0;i<n;i++){
if(i<x){
pq2.push({cost1[i],i});
}
if(x<=i&&i<=y){
pq2.push({cost2[i],i});
curk+=cost1[i];
vis[i]=1;
ans2++;
}
if(y<i){
pq2.push({cost1[i],i});
}
}
if(curk>k){
return ans1;
}
while(curk<=k){
pair<long long,int>p = pq2.top();
pq2.pop();
long long a = p.first;
int i = p.second;
if(curk+a>k)
break;
ans2++;
curk+=a;
if(vis[i])
continue;
vis[i]=1;
pq2.push({cost2[i],i});
}
return max(ans1,ans2);
}
