#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3000;
#define MID ((l+r)/2)
ll prefa[N], prefb[N], prefmax[N];
ll suma(ll l, ll r){
if(r<l) return 0;
else if(l==0) return prefa[r];
else return prefa[r]-prefa[l-1];
}
ll sumb(ll l, ll r){
if(r<l) return 0;
else if(l==0) return prefb[r];
else return prefb[r]-prefb[l-1];
}
ll summax(ll l, ll r){
if(r<l) return 0;
else if(l==0) return prefmax[r];
else return prefmax[r]-prefmax[l-1];
}
vector<pair<ll,ll>> g[N];
ll idx[N];
void dfs(ll curr, ll prev){
idx[curr]=idx[prev]+1;
for(auto nxt:g[curr]){
if(nxt.first!=prev) dfs(nxt.first,curr);
}
}
ll dista[N], distb[N];
void dfsa(ll curr, ll prev, ll d){
dista[idx[curr]]=d;
for(auto nxt:g[curr]){
if(nxt.first!=prev) dfsa(nxt.first,curr,d+nxt.second);
}
}
void dfsb(ll curr, ll prev, ll d){
distb[idx[curr]]=d;
for(auto nxt:g[curr]){
if(nxt.first!=prev) dfsb(nxt.first,curr,d+nxt.second);
}
}
int max_score(int n, int a, int b, long long k, vector<int> u, vector<int> v, vector<int> w){
for(ll i=0; i<n; i++){
g[i].clear();
}
for(ll i=0; i<n-1; i++){
g[u[i]].push_back({v[i],w[i]});
g[v[i]].push_back({u[i],w[i]});
}
for(ll i=0; i<n; i++){
if(g[i].size()==1){
idx[i]=-1;
dfs(i,i);
break;
}
}
if(idx[a]>idx[b]) swap(a,b);
dfsa(a,a,0);
dfsb(b,b,0);
a=idx[a];
b=idx[b];
prefa[0]=dista[0];
prefb[0]=distb[0];
prefmax[0]=max(dista[0],distb[0]);
for(ll i=1; i<n; i++){
prefa[i]=prefa[i-1]+dista[i];
prefb[i]=prefb[i-1]+distb[i];
prefmax[i]=prefmax[i-1]+max(dista[i],distb[i]);
}
vector<ll> x;
for(ll i=0; i<a; i++){
x.push_back(dista[i]);
}
for(ll i=b+1; i<n; i++){
x.push_back(distb[i]);
}
sort(x.begin(),x.end());
for(ll i=1; i<x.size(); i++){
x[i]+=x[i-1];
}
ll ans=0;
for(ll ra=a; ra<n; ra++){
for(ll lb=0; lb<=b; lb++){
ll s;
if(ra<lb) s=suma(a,ra)+sumb(lb,b);
else s=summax(lb,ra)+suma(a,lb-1)+sumb(ra+1,b);
if(s>k) continue;
ll l=0, r=x.size()-1, y=0;
while(l<=r){
if(s+x[MID]<=k){
y=MID+1;
l=MID+1;
}
else r=MID-1;
}
ans=max(ans,y+(ra-a+1)+(b-lb+1));
}
}
return ans;
}
