#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const long long N=4e5+5;

vector <long long> g[N],w[N];
long long fat[N],fa[N],son[N],a[N],n;
long long distx[N],disty[N];
bool inpath[N];

void dfsx(long long x,long long fa)
{
	for(long long i=0;i<g[x].size();i++)
	{
		long long to=g[x][i];
		if(to==fa)
			continue;

		fat[to]=x;
		distx[to]=distx[x]+w[x][i];
		dfsx(to,x);
	}
}

void dfsy(long long x,long long fa)
{
	for(long long i=0;i<g[x].size();i++)
	{
		long long to=g[x][i];
		if(to==fa)
			continue;

		disty[to]=disty[x]+w[x][i];
		dfsy(to,x);
	}
}

long long calc(long long k)
{
	priority_queue <long long,vector <long long>,greater<long long> > q;
	for(long long i=1;i<=n;i++)
		q.push(distx[i]);

	for(long long i=1;i<=n;i++)
		q.push(disty[i]);

	long long ans=0;
	while(!q.empty())
	{
		long long x=q.top();
		q.pop();
		k -= x, ans++;
		if(k<0)
			return ans-1;
	}
	return ans;
}

void add(long long x,long long y,long long z)
{
	g[x].push_back(y);
	w[x].push_back(z);
}

struct node
{
	long long sz,sum;
	long long id;

	bool operator <(const node& oth) const
	{
		return sum*oth.sz>oth.sum*sz;
	}
}val[N];

bool del[N],in[N];
pair <long long,long long> edge[N];
long long sumfirst[N];
long long cnt;
priority_queue <pair<long long,long long>,vector <pair<long long,long long> >,greater<pair<long long,long long> > > q;

long long gettop()
{
	while(del[q.top().second])
		q.pop();

	in[q.top().second]=true;
	long long ans=q.top().first;
	q.pop();
	return ans;
}

bool check(long long m,long long k) //判断是否可以取m个，上界为k
{
	if(m==cnt*2+1)
		return false;

	while(!q.empty())
		q.pop();

	for(long long i=1;i<=cnt*2;i++)
		del[i]=in[i]=false;

	sort(edge+1,edge+cnt+1);
	for(long long i=1;i<=cnt;i++) //处理第一行的前缀和
		sumfirst[i]=sumfirst[i-1]+edge[i].second;

	for(long long i=1;i<=cnt;i++)
		q.push(make_pair(edge[i].first-edge[i].second,i+cnt)); //第一行的标号为i，第二行的标号为i+cnt

	long long nowsum=0;
	for(long long i=1;i<=m-cnt;i++)
		nowsum += gettop();

	for(long long i=cnt;i>=0;i--) //[1,i]都取了第一行，这些列的决策都为“第二行”，[i+1,n]都不能取第二行，决策为“第一行”
	{ //要维护前m-i小的和
		if(i>m)
			continue;

		if(nowsum+sumfirst[i]<=k) //当前这个i是合法的
			return true;

		if(i+cnt<=m)
			return false;

		//更新nowsum
		q.push(make_pair(edge[i].second,i));
		nowsum += gettop();

		del[i+cnt]=true;
		if(in[i+cnt])
		{
			in[i+cnt]=false;
			nowsum -= edge[i].first-edge[i].second;
			nowsum += gettop();
		}
	}

	return false;
}

void add(long long x,long long y)
{
	edge[++cnt]=make_pair(x+y,x);
}

int max_score(int N, int x, int y, long long k, vector<int> U, vector<int> V, vector<int> W)
{
	n=N, x++, y++, cnt=0;
	for(long long i=1;i<=n;i++)
		g[i].clear(), w[i].clear(), inpath[i]=false, distx[i]=disty[i]=fat[i]=0;

	for(long long i=0;i<n-1;i++)
	{
		add(U[i]+1,V[i]+1,W[i]);
		add(V[i]+1,U[i]+1,W[i]);
	}

	dfsx(x,-1), dfsy(y,-1);
	for(long long i=1;i<=n;i++)
		g[i].clear();

	for(long long i=0;i<=n*2;i++)
		fa[i]=son[i]=del[i]=0;

	long long sum=0,cnt=0,ans=calc(k);
	for(long long i=y;i;i=fat[i])
	{
		inpath[i]=true;
		if(distx[i]>disty[i]) swap(distx[i],disty[i]);

		add(0,disty[i]-distx[i]);
		k -= distx[i], sum++;
		val[cnt+1].sum=disty[i]-distx[i];
		cnt++;
	}

	long long realk=k;
	if(k<0)
		return ans;

	for(long long i=1;i<=n;i++)
	{
		if(!inpath[i])
		{
			if(distx[i]>disty[i]) swap(distx[i],disty[i]);

			add(distx[i],disty[i]-distx[i]);
			val[cnt+2].sum=disty[i]-distx[i], val[cnt+1].sum=distx[i];
			fa[cnt+2]=cnt+1, son[cnt+1]=cnt+2;
			cnt += 2;
		}
	}

	priority_queue <node> q;
	for(long long i=1;i<=cnt;i++)
	{
		val[i].sz=1, val[i].id=i;
		q.push(val[i]), a[i]=val[i].sum;
	}

	while(!q.empty())
	{
		node x=q.top();
		q.pop();
		if(del[x.id])
			continue;

		if(!fa[x.id] || del[fa[x.id]])
		{
			if(k>=x.sum)
			{
				k -= x.sum;
				sum += x.sz;
				if(x.sz==1)
					del[x.id]=true;
				else
					del[x.id]=del[son[x.id]]=true;
				continue;
			}
			else
				break;
		}
		else
		{
			val[fa[x.id]].sz += val[x.id].sz, val[fa[x.id]].sum += x.sum;
			q.push(val[fa[x.id]]);
		}
	}

	for(long long i=1;;i++)
		if(!check(i,realk))
			return max(i-1,ans);
}