#include "closing.h"

#include <bits/stdc++.h>
using namespace std;
long long disx[200005],disy[200005];
vector<pair<int,int> >v[200005];
void dfsx(int x,int f)
{
	for(int i=0;i<v[x].size();i++)
	{
		int sth=v[x][i].first,bq=v[x][i].second;
		if(sth==f)continue;
		disx[sth]=disx[x]+bq;
		dfsx(sth,x);
	}
}
void dfsy(int x,int f)
{
	for(int i=0;i<v[x].size();i++)
	{
		int sth=v[x][i].first,bq=v[x][i].second;
		if(sth==f)continue;
		disy[sth]=disy[x]+bq;
		dfsy(sth,x);
	}
}
long long dis1[200005],dis2[200005];
long long dp[3005][6005];
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
	for(int i=1;i<=N;i++)v[i].clear();
	for(int i=0;i<N-1;i++)
	{
		U[i]++;
		V[i]++;
		v[U[i]].push_back(make_pair(V[i],W[i]));
		v[V[i]].push_back(make_pair(U[i],W[i]));
	}
	X++;
	Y++;
	disx[X]=disy[Y]=0;
	dfsx(X,0);
	dfsy(Y,0);
	for(int i=1;i<=N;i++)
	{
		dis1[i]=min(disx[i],disy[i]);
		dis2[i]=max(disx[i],disy[i]);
	}
	dp[0][0]=0;
	for(int i=1;i<=2*N;i++)dp[0][i]=1121131433448687LL;
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<=2*N;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(j>=1)dp[i][j]=min(dp[i][j],dp[i-1][j-1]+dis1[i]);
			if(j>=2)dp[i][j]=min(dp[i][j],dp[i-1][j-2]+dis2[i]);
		}
	}
	for(int i=1;i<=2*N;i++)if(K<dp[N][i])return i-1;
    return 2*N;
}