#include "closing.h"

#include <bits/stdc++.h>
using namespace std;
long long disx[200005],disy[200005];
vector<pair<int,int> >v[200005];
int fa[200005];
bool lj[200005];
void dfsx(int x,int f)
{
	fa[x]=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];
long long qz[200005];
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(),lj[i]=false;
	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);
	int sth=Y;
	while(sth!=0)
	{
		lj[sth]=true;
		sth=fa[sth];
	}
	int ans1=N;
	for(int i=1;i<=N;i++)
	{
		dis1[i]=min(disx[i],disy[i]);
		dis2[i]=max(disx[i],disy[i]);
		qz[i]=dis1[i];
		//printf("%lld %lld\n",dis1[i],dis2[i]);
	}
	sort(qz+1,qz+N+1);
	int now=0;
	for(int i=1;i<=N;i++)
	{
		now+=qz[i];
		if(now>K)
		{
			ans1=i-1;
			break;
		}
	}
	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(lj[i])dp[i][j]=1121131433448687LL;
			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]);
			//printf("%d %d %lld\n",i,j,dp[i][j]);
		}
	}
	int ans2=0;
	for(int i=1;i<=2*N;i++)if(K>=dp[N][i])
	{
		ans2=max(ans2,i);
	}
    return max(ans1,ans2);
}