#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;
vector<vector<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){
adj.resize(n,vector<int>(n));
lst.resize(n);
distx.resize(n,0);
disty.resize(n,0);
seen.resize(n,0);
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();
}
