#include <bits/stdc++.h>
#define int long long
#define REP(i,a,b) for(int i = a; i<b; i++)
#define RREP(i,a,b) for(int i = a; i>b; i--)
using namespace std;
int INF = 1e18;
map<pair<int,int>,int> adj;
vector<vector<int>> lst;
vector<pair<int,int>> len;
vector<int> seen;
vector<int> distx;
vector<int> disty;
void dfsx(int node,int parent){
for(int child: lst[node]){
if(child == parent) continue;
distx[child] = distx[node] + adj[{child,node}];
len.push_back({distx[child],child});
dfsx(child,node);
}
}
void dfsy(int node,int parent){
for(int child: lst[node]){
if(child == parent) continue;
disty[child] = disty[node] + adj[{child,node}];
len.push_back({disty[child],child});
dfsy(child,node);
}
}
int max_score(int32_t n, int32_t x, int32_t y, int k, vector<int32_t> u, vector<int32_t> v, vector<int32_t> w){
lst.assign(n,vector<int>(0));
distx.assign(n,0);
disty.assign(n,0);
seen.assign(n,0);
len.clear();
REP(i,0,n-1){
adj[{u[i],v[i]}] = w[i];
adj[{v[i],u[i]}] = w[i];
lst[u[i]].push_back(v[i]);
lst[v[i]].push_back(u[i]);
}
distx[x] = 0;
len.push_back({0,x});
dfsx(x,x);
disty[y] = 0;
len.push_back({0,y});
dfsy(y,y);
sort(len.begin(),len.end());
int sum = 0;
REP(i,0,len.size()){
sum+=len[i].first;
sum-=seen[len[i].second];
seen[len[i].second]+=len[i].first;
if(sum>k){
return i;
}
}
return len.size();
}
