#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
#include <bits/stdc++.h>
using namespace std;
ll dst1[200007],dst2[200007];
vector<pair<ll,ll>>g[200007];
void dfs1(ll v,ll pop,ll dst){
dst1[v]=dst;
for(pair<ll,ll> i : g[v]){
if(i.ff!=pop){
dfs1(i.ff,v,dst+i.ss);
}
}
}
void dfs2(ll v,ll pop,ll dst){
dst2[v]=dst;
for(pair<ll,ll> i : g[v]){
if(i.ff!=pop){
dfs2(i.ff,v,dst+i.ss);
}
}
}
int max_score(int n,int x,int y,ll k,vector<int>u,vector<int>v,vector<int>w){
for(ll i=0;i<n+7;i++){
g[i].clear();
}
for(ll i=0;i<n-1;i++){
g[u[i]].pb({v[i],w[i]});
g[v[i]].pb({u[i],w[i]});
}
dfs1(x,-1,0);
dfs2(y,-1,0);
vector<ll>v1,v3;
vector<pair<ll,ll>>v2;
ll K=k;
ll dod=0;
for(ll i=0;i<n;i++){
v3.pb(min(dst1[i],dst2[i]));
if(dst1[i]+dst2[i]==dst2[x]){
//cout<<i<<" ";
v1.pb(max(dst1[i],dst2[i])-min(dst1[i],dst2[i]));
dod++;
K-=min(dst1[i],dst2[i]);
}
else{
if(min(dst1[i],dst2[i])*2<=max(dst1[i],dst2[i])){
v1.pb(min(dst1[i],dst2[i]));
v1.pb(max(dst1[i],dst2[i])-min(dst1[i],dst2[i]));
}
else{
v2.pb({max(dst1[i],dst2[i]),min(dst1[i],dst2[i])});
}
}
}
ll wyn1=0;
ll pom=k;
//cout<<k<<" ";
sort(v3.begin(),v3.end());
for(ll i=0;i<n;i++){
if(pom-v3[i]<0)break;
pom-=v3[i];
//cout<<"xd";
wyn1++;
}
if(K<0)return wyn1;
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
multiset<ll>s1,s2;
ll ak=v2.size();//pierwszy niewiziety
ll akwyn=2*v2.size()+dod-1;
for(pair<ll,ll> i : v2){
K-=i.ff;
s1.insert(i.ff-i.ss);
}
for(ll i=0;i<=v1.size();i++){
if(i){
K-=v1[i-1];
}
akwyn++;
while(K<0){
if(ak==0)return wyn1;
akwyn-=2;
K+=v2[--ak].ff;
s1.erase(s1.lower_bound(v2[ak].ff-v2[ak].ss));
s2.insert(v2[ak].ss);
}
ll czy=0;
if(s2.size() && *s2.begin()<=K)czy=1;
if(s1.size() && (*--s1.end())+K>=v2[ak].ff)czy=1;
wyn1=max(wyn1,akwyn+czy);
}
return wyn1;
}
