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

const int N=4e5+5;

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

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

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

void dfsy(int x,int fa)
{
	for(int i=0;i<g[x].size();i++)
	{
		int 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(int i=1;i<=n;i++)
		q.push(distx[i]);

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

	int 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(int x,int y,int z)
{
	g[x].push_back(y);
	w[x].push_back(z);
}

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

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

bool del[N];

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++;
	for(int i=1;i<=n;i++)
		g[i].clear(), w[i].clear(), inpath[i]=false, distx[i]=disty[i]=fat[i]=0;

	for(int 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(int i=1;i<=n;i++)
		g[i].clear();

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

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

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

	if(k<0)
		return ans;

	for(int i=1;i<=n;i++)
	{
		if(!inpath[i])
		{
			if(distx[i]>disty[i]) swap(distx[i],disty[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(int i=1;i<=cnt;i++)
	{
		val[i].sz=1, val[i].id=i;
		q.push(val[i]), a[i]=val[i].sum;
	}

	int maxone=0;
	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, maxone=max(maxone,a[x.id]);
				else
					del[x.id]=del[son[x.id]]=true;
				continue;
			}
			else
			{
				if(x.sz==1)
					return max(sum,ans);

				if(k+maxone>=x.sum)
					return max(sum+1,ans);

				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(int i=1;i<=cnt;i++)
		if((!fa[i] || del[fa[i]]) && !del[i] && k>=a[i])
			return max(sum+1,ans);

	return max(sum,ans);
}