/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#include"closing.h"
int max_score(int n,int x,int y,ll k,vector<int>U,vector<int>V,vector<int>W);
struct sgt{
vector<ll>s,c;
int lg,sz;
sgt(int n){
lg=__lg(n)+1;
sz=1<<lg;
s.assign(sz*2,0);c=s;
}
void add(int i,ll v){
i+=sz;
s[i]+=v;
c[i]=1;
while(i>1){
i>>=1;
s[i]=s[i*2]+s[i*2+1];
c[i]=c[i*2]+c[i*2+1];
}
}
void del(int i){
i+=sz;s[i]=c[i]=0;
while(i>1){
i>>=1;
s[i]=s[i*2]+s[i*2+1];
c[i]=c[i*2]+c[i*2+1];
}
}
ll get(ll L,ll R,ll l,ll r,ll i){
if(l>R||L>r)return 0;
if(L<=l&&r<=R)return c[i];
return get(L,R,l,(l+r)/2,i*2)+get(L,R,(l+r)/2+1,r,i*2+1);
}
ll get(ll k){
ll i=1,tot=0;
while(i<sz){
if(tot+s[i*2]<=k){tot+=s[i*2];i=i*2+1;}
else i*=2;
}
if(s[i]+tot<=k)i++;
return get(1,i-sz,1,sz,1);
}
};
const ll inf=1e18;
int max_score(int n,int x,int y,ll k,vector<int>U,vector<int>V,vector<int>W){
vector<vector<array<ll,2>>>a(n);
int sbt=1;
for(int i=0;i+1<n;i++){
a[U[i]].push_back({V[i],W[i]});
a[V[i]].push_back({U[i],W[i]});
sbt&=V[i]==U[i]+1;
}
ll ans=0;
queue<int>q;
vector<array<ll,2>>d(n,{inf,inf});
d[x][0]=0;q.push(x);
while(!q.empty()){
int i=q.front();q.pop();
for(auto&[j,w]:a[i]){
if(d[j][0]==inf){d[j][0]=d[i][0]+w;q.push(j);}
}
}
d[y][1]=0;q.push(y);
while(!q.empty()){
int i=q.front();q.pop();
for(auto&[j,w]:a[i]){
if(d[j][1]==inf){d[j][1]=d[i][1]+w;q.push(j);}
}
}
vector<int>vis(n,0);
multiset<array<ll,2>>s;
for(int i=0;i<n;i++){
s.insert({d[i][0],i});
s.insert({d[i][1],i});
}
ll kk=k;
for(int cnt=0;cnt<n;cnt++){
ll i=(*s.begin())[1],c=(*s.begin())[0];
s.erase(s.find(*s.begin()));
if(vis[i]||c>kk)break;
vis[i]++;
kk-=c;ans++;
}
if(sbt){
vector<ll>p(n,0);
for(int i=0;i+1<n;i++)p[i+1]=p[i]+a[i][(a[i][1][0]==i+1)][1];
auto dis=[&](int i,int j)->ll{
if(i>j)swap(i,j);
return p[j]-p[i];
};
for(int l=0;l<=y;l++){
int r=max(x,l);
ll v=0;
for(int i=l;i<=r;i++)v+=max(dis(i,x),dis(i,y));
for(int i=r+1;i<=y;i++)v+=dis(i,y);
for(int i=x;i<l;i++)v+=dis(i,x);
vector<array<ll,2>>vl;
for(int i=0;i<min(l,x);i++)vl.push_back({dis(i,x),i});
for(int i=max(y,r)+1;i<n;i++)vl.push_back({dis(i,y),i});
sort(vl.begin(),vl.end());
vector<int>val(n);
for(int i=0;i<vl.size();i++)val[vl[i][1]]=i;
sgt s(vl.size());
for(int i=0;i<vl.size();i++)s.add(i,vl[i][0]);
if(v<=k)ans=max(ans,(r-l+1)*2+max(0,l-x)+max(0,y-r)+s.get(k-v));
while(++r<n){
if(r<=y)v+=max(0LL,dis(r,x)-dis(r,y));
else v+=dis(r,x);
if(r>y)s.del(val[r]);
if(v<=k)ans=max(ans,(r-l+1)*2+max(0,l-x)+max(0,y-r)+s.get(k-v));
}
}
return ans;
}
if(d[y][0]<=2*k){
bool v[25],ff[25]{};
vector<ll>q;
vector<bool>f[25];
vector<int>c;
auto calc=[&](int i,int p,auto&calc)->void{
c.push_back(i);
if(v[i]){
for(int i=c.size()-1;i>=0&&ff[c[i]]==0;i--)ff[c[i]]=1;
}
for(auto&[j,k]:a[i])if(j!=p)calc(j,i,calc);
c.pop_back();
};
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++)v[j]=(i>>j)&1;
calc(x,-1,calc);
for(int j=0;j<n;j++)if(ff[j]){f[j].push_back(0);ff[j]=0;}
calc(y,-1,calc);
for(int j=0;j<n;j++)if(ff[j]){f[j].push_back(1);ff[j]=0;}
ll tot=0,mx;
for(int j=0;j<n;j++){
mx=0;
for(const int&jj:f[j])mx=max(mx,d[j][jj]);
tot+=mx;
}
if(tot<=k){
ll kk=k-tot,aans=0;
q.clear();
for(int j=0;j<n;j++){
if(f[j].empty()){
q.push_back(min(d[j][0],d[j][1]));
}
aans+=f[j].size();
}
sort(q.begin(),q.end());
for(int ii=0;ii<q.size()&&kk>=q[ii];ii++){
kk-=q[ii];aans++;
}
ans=max(aans,ans);
}
for(int j=0;j<n;j++)f[j].clear();
}
}
return ans;
}
