#include<bits/stdc++.h>
#define MAXN 3007
using namespace std;
const long long inf=1000000000000000007;
int n,x,y,sz[2*MAXN],num,ans;
vector< pair<int,int> > v[MAXN];
vector<int> w[2*MAXN];
int path[MAXN],szp,pref[MAXN];
long long dist[MAXN][2];
bool special[MAXN];
long long dp[2*MAXN][2*MAXN][3];
long long dp2[MAXN][2*MAXN][3];
void reset(){
for(int i=1;i<=n;i++){
special[i]=false;
v[i].clear();
}
szp=0; ans=0;
for(int i=1;i<=2*n;i++){
w[i].clear(); sz[i]=0;
}
}
int greedy(long long K){
vector<long long> vals;
for(int i=1;i<=n;i++){
vals.push_back(dist[i][0]);
vals.push_back(dist[i][1]);
}
sort(vals.begin(),vals.end());
int res=0;
for(int i=0;i<vals.size();i++){
K-=vals[i];
if(K<0)break;
res++;
}
return res;
}
void dfs(int x,int p,int id,long long d){
dist[x][id]=d;
for(auto nxt:v[x]){
if(nxt.first==p)continue;
dfs(nxt.first,x,id,d+nxt.second);
}
}
bool findv(int x,int p,int y){
if(x==y){
special[y]=true;
szp++; path[szp]=y;
return true;
}
for(auto nxt:v[x]){
if(nxt.first==p)continue;
if(findv(nxt.first,x,y)){
special[x]=true;
szp++; path[szp]=x;
return true;
}
}
return false;
}
void build(int x,int p){
vector<int> c;
for(auto nxt:v[x]){
if(nxt.first==p or special[nxt.first])continue;
build(nxt.first,x);
c.push_back(nxt.first);
}
if(c.empty())return;
if(c.size()==1){
w[x].push_back(c[0]);
return;
}
int curr=c[0];
for(int i=1;i<int(c.size())-1;i++){
num++;
w[num].push_back(curr);
w[num].push_back(c[i]);
curr=num;
}
w[x].push_back(curr);
w[x].push_back(c.back());
}
void dfs2(int x){
sz[x]=(x<=n);
for(auto nxt:w[x]){
dfs2(nxt);
sz[x]+=sz[nxt];
}
}
long long cost(int x,int s){
if(s==0)return dist[x][0];
if(s==1)return dist[x][1];
return max(dist[x][0],dist[x][1]);
}
void calcdp(int x){
for(auto nxt:w[x]){
calcdp(nxt);
}
for(int ver=0;ver<3;ver++){
for(int k=0;k<=2*sz[x];k++){
if((ver<2 and k>sz[x])){
dp[x][k][ver]=inf;
continue;
}
dp[x][k][ver]=inf;
if(ver==2 and !special[x]){
dp[x][k][ver]=min(dp[x][k][0],dp[x][k][1]);
}
if(k==0){
dp[x][k][ver]=0;
continue;
}
int coef=ver/2+1;
if(x>n){
for(int s=k-coef*sz[w[x][1]];s<=coef*sz[w[x][0]];s++){
if(s<0)continue;
if(k-s<0)continue;
dp[x][k][ver]=min(dp[x][k][ver] , dp[w[x][0]][s][ver] + dp[w[x][1]][k-s][ver] );
}
}else{
int red=ver/2+1;
if(w[x].empty()){
dp[x][k][ver]=min(dp[x][k][ver],cost(x,ver));
}else if(w[x].size()==1){
if(k-red<=0)dp[x][k][ver]=min(dp[x][k][ver],cost(x,ver));
else dp[x][k][ver]=min(dp[x][k][ver],dp[w[x][0]][k-red][ver] + cost(x,ver));
}else{
for(int s=k-red-coef*sz[w[x][1]];s<=coef*sz[w[x][0]];s++){
if(s<0)continue;
if(k-red-s<0)continue;
dp[x][k][ver]=min(dp[x][k][ver] , dp[w[x][0]][s][ver] + dp[w[x][1]][k-red-s][ver] + cost(x,ver) );
}
}
}
}
}
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){
n=N; x=X+1; y=Y+1;
reset();
for(int i=0;i<n-1;i++){
v[U[i]+1].push_back({V[i]+1,W[i]});
v[V[i]+1].push_back({U[i]+1,W[i]});
}
dfs(x,0,0,0);
dfs(y,0,1,0);
findv(x,0,y);
reverse(path+1,path+szp+1);
num=n;
for(int i=1;i<=n;i++){
if(special[i]){
build(i,0);
dfs2(i);
calcdp(i);
}
}
for(int k=1;k<=2*n;k++){
dp2[0][k][0]=dp2[0][k][1]=dp2[0][k][2]=inf;
}
for(int i=1;i<=szp;i++){
pref[i]=pref[i-1]+sz[path[i]];
}
for(int i=1;i<=szp;i++){
for(int k=i;k<=2*n;k++){
for(int state=0;state<=2;state++){
dp2[i][k][state]=inf;
if(state>0)dp2[i][k][state]=dp2[i][k][state-1];
int coef=1;
if(state==1)coef=2;
int ver=3-state;
if(ver==3)ver=0;
int ptr=2;
if(state==0)ptr=1;
for(int t=max(1,k-pref[i-1]*ptr);k-t>=i-1 and t<=coef*sz[path[i]];t++){
dp2[i][k][state]=min(dp2[i][k][state],dp[path[i]][t][ver] + dp2[i-1][k-t][state]);
}
}
}
}
for(int i=2*n;i>=szp;i--){
if(dp2[szp][i][2]<=K){
ans=i; break;
}
}
ans=max(ans,greedy(K));
return ans;
}
/*int main(){
cout<<max_score(7, 0, 2, 10,
{0, 0, 1, 2, 2, 5}, {1, 3, 2, 4, 5, 6}, {2, 3, 4, 2, 5, 3})<<"\n";
cout<<max_score(4, 0, 3, 20, {0, 1, 2}, {1, 2, 3}, {18, 1, 19})<<"\n";
return 0;
}*/
