#include <vector>
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int mx=2e5+12;
vector<pair<int,long long>> g[mx];
long long d[mx];
long long d1[mx];
long long d2[mx];
int p1[mx];
int p2[mx];
int A[mx];
long long n,k;
bool ok=0;
void dfs(int v,int p,bool ok){
for(auto To:g[v]){
int to=To.f,w=To.s;
if(to==p){
continue;
}
if(ok){
p2[to]=v;
d2[to]=d2[v]+w;
}
else{
p1[to]=v;
d1[to]=d1[v]+w;
}
dfs(to,v,ok);
}
}
void dfs1(int v,int p,int d,int mask){
d=min(d,A[v]);
if(!d && A[v]){
ok=1;
}
for(auto To:g[v]){
if(To.f!=p){
dfs1(To.f,v,d,mask);
}
}
}
int max_score(int N, int x, int y, long long K, std::vector<int> U,std::vector<int> V, std::vector<int> W){
n=N,k=K;
for(int i=0;i<n;i++){
g[i].clear();
d1[i]=d2[i]=0;
p1[i]=p2[i]=-1;
}
for(int i=0;i<n-1;i++){
g[V[i]].push_back({U[i],W[i]});
g[U[i]].push_back({V[i],W[i]});
}
dfs(x,-1,0);
dfs(y,-1,1);
vector<int> a,b;
for(int mask=0;mask<(1<<n);mask++){
for(int i=0;i<n;i++){
A[i]=0;
if((mask&(1<<i))){
A[i]=1;
}
}
ok=0;
dfs1(x,-1,1,mask);
if(!ok){
a.push_back(mask);
}
ok=0;
dfs1(y,-1,1,mask);
if(!ok){
b.push_back(mask);
}
}
int ans=0;
for(int x:a){
for(int y:b){
long long sum=0;
int cnt=0;
for(int i=0;i<n;i++){
long long t=0;
if(((1<<i)&x)){
t=d1[i];
cnt++;
}
if(((1<<i)&y)){
t=max(t,d2[i]);
cnt++;
}
sum+=t;
}
if(sum<=k){
ans=max(ans,cnt);
}
}
}
return ans;
}
