#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[400005];
int sy[200005];
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > >pq,pq2;
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(),sy[i]=0;
	while(!pq.empty())pq.pop();
	while(!pq2.empty())pq2.pop();
	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);
	long long now=0;
	for(int i=1;i<=N;i++)
	{
		now+=qz[i];
		if(now>K)
		{
			ans1=i-1;
			break;
		}
	}
	int ans2=0;
	int nsl=0;
	long long het=0;
	for(int i=1;i<=N;i++)
	{
		if(lj[i])
		{
			nsl++;
			het+=dis1[i];
			sy[i]=1;
			pq.push(make_pair(dis2[i]-dis1[i],i));
		}
		else
		{
			if(dis1[i]<dis2[i]-dis1[i])
			{
				pq.push(make_pair(dis1[i],i));
				pq.push(make_pair(dis2[i]-dis1[i],i)); 
			}
			else
			{
				pq2.push(make_pair(dis2[i],i));
			}
		}
	}
	if(het>K)return ans1;
	while(!pq2.empty())
	{
		pair<long long,int> sth=pq2.top();
		//printf("!!!%lld %d\n",sth.first,sth.second);
		if(het+sth.first>K)
		{
			break;
		}
		if(pq.size()<=1)
		{
			het+=sth.first;
			sy[sth.second]+=2;
			nsl+=2;
			pq2.pop();
			continue;
		}
		pair<long long,int> x=pq.top();
		pq.pop();
		pair<long long,int> y=pq.top();
		if(x.first+y.first<sth.first)
		{
			//printf("pq:%lld %d\n",x.first,x.second);
			het+=x.first;
			sy[x.second]+=1;
			nsl++;
		}
		else
		{
			//printf("pq2:%lld %d\n",sth.first,sth.second);
			het+=sth.first;
			nsl+=2;
			sy[sth.second]+=2;
			pq.push(x);
			pq2.pop();			
		}
	}
	//printf("!!!%lld %d\n",het,nsl);
	int tmp=0;
	for(int i=1;i<=N;i++)
	{
		if(sy[i]==0)
		{
			qz[++tmp]=dis1[i];
		}
		if(sy[i]<2)
		{
			qz[++tmp]=dis2[i]-dis1[i];
		}
	}
	sort(qz+1,qz+tmp+1);
	for(int i=1;i<=tmp;i++)
	{
		if(het+qz[i]<=K)
		{
			het+=qz[i];
			nsl++;
		}
	}
	//printf("!!!%lld %d\n",het,nsl);
	ans2=nsl;
    return max(ans1,ans2);
}