#include "closing.h"
using namespace std;
#include <bits/stdc++.h>
#define pb push_back
using lli=long long;
#define deb(x) cout<<#x<<": "<<x<<endl;
int max_score(int N, int X, int Y, long long K,
vector<int> U, vector<int> V, vector<int> W)
{
lli ans=0;
vector<vector<pair<lli,lli>>> adj (N);
lli mat [N][N];
for(lli i=0; i<N-1; ++i){
adj[U[i]].pb({V[i], W[i]});
adj[V[i]].pb({U[i], W[i]});
mat[U[i]][V[i]]=W[i];
mat[V[i]][U[i]]=W[i];
}
lli init=0;
lli last=0;
lli ant=0;
while(adj[init].size()==2){
if(adj[init][0].first!=ant){
ant=init;
init=adj[init][0].first;
}
else{
ant=init;
init=adj[init][1].first;
}
}
ant=init;
last=adj[init][0].first;
while(adj[last].size()==2){
if(adj[last][0].first!=ant){
ant=last;
last=adj[last][0].first;
}
else{
ant=last;
last=adj[last][1].first;
}
}
vector<lli> ord;
lli rec=init;
ant=init;
while(rec!=last){
// cout<<"rec: "<<rec<<endl;
ord.pb(rec);
if(adj[rec][0].first!=ant){
ant=rec;
rec=adj[rec][0].first;
}
else{
ant=rec;
rec=adj[rec][1].first;
}
}
ord.pb(rec);
vector<lli> numb(N);
for(lli i=0; i<N; ++i){
numb[ord[i]]=i;
}
if(numb[X]>numb[Y]){
swap(X,Y);
}
for(lli i=numb[X]; i>=0; --i){
vector<lli> values (N, 0);
lli cont=K;
for(lli a=numb[X]-1; a>=i; --a){
values[a]=values[a+1]+mat[ord[a+1]][ord[a]];
cont-=values[a];
}
if(cont<0) break;
lli ayuda=cont;
for(lli j=numb[X]; j<N; ++j){
cont=ayuda;
if(j>numb[X]){
values[j]=values[j-1]+mat[ord[j-1]][ord[j]];
ayuda-=values[j];
cont=ayuda;
}
if(cont<0) break;
lli aux=j-i+1;
priority_queue<pair<pair<lli,lli>,lli>, vector<pair<pair<lli,lli>,lli>>, greater<pair<pair<lli,lli>,lli>>> pq;
vector<bool> visited (N, false);
pq.push({{0,0}, numb[Y]});
while(!pq.empty()){
lli a=pq.top().first.first;
lli c=pq.top().first.second;
lli b=pq.top().second;
pq.pop();
if(visited[b]) continue;
visited[b]=true;
if(cont>=a){
cont-=a;
aux++;
if(b+1<N && !visited[b+1]){
pq.push({{max(c+mat[ord[b]][ord[b+1]]-values[b+1],0ll),c+mat[ord[b]][ord[b+1]]}, b+1});
}
if(b-1>=0 && !visited[b-1]){
pq.push({{max(c+mat[ord[b]][ord[b-1]]-values[b-1],0ll),c+mat[ord[b]][ord[b-1]]}, b-1});
}
}
else{
break;
}
}
ans=max(ans, aux);
}
}
return ans;
}
