#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define pp push
vector<vector<pair<int,ll>>> graph;
vector<bool> vis;
vector<ll> seg1,seg2;

struct node{
	ll t;
	int x, cnt = 0;
	bool operator<(const node &b) const
    {
        return t < b.t;
    }
    bool operator>(const node &b) const
    {
        return b < (*this);
    }
};

int greedy(int N, int mx, ll k, ll mdist) {
    //cout <<"1\n";
	int ans = 0;
	vector<int> cnt(N, 0);
	priority_queue<node, vector<node>, greater<node>> pqa, pqb;
    //cout <<"1\n";
	for (int i = 0; i < N; i ++) {
		if (mx == 2 && seg1[i] + seg2[i] == mdist) {// case 1 a's
			ans++;
			cnt[i] ++;
			k -= min(seg1[i], seg2[i]);
            pqa.pp({abs(seg1[i] - seg2[i]), i, 1});
		} else  { 
			pqa.pp({min(seg1[i], seg2[i]), i ,0});
			if (mx == 2 ) {// case 2 the b's
				pqb.pp({max(seg1[i], seg2[i]), i , 0});
			}
		}
	}
    //cout <<"1\n";
	 auto get_top = [](priority_queue<node, vector<node>, greater<node>> &pq) -> node
    {
        return pq.empty() ? node{(ll)1e18, (ll)0} : pq.top();
    };

    auto reduce = [&cnt, &mx, &k](priority_queue<node, vector<node>, greater<node>> &pq) -> void
    {
        while (!pq.empty() && (cnt[pq.top().x] != pq.top().cnt || k < pq.top().t))
        {
            pq.pop();
        }
    };
    //cout <<"1\n";
    while (!pqa.empty() || !pqb.empty())
    {
        reduce(pqa);
        reduce(pqb);
        if (pqa.empty() && pqb.empty())
            break;
        node one1 = get_top(pqa), one2;
        if (!pqa.empty())
        {
            pqa.pop();
            cnt[one1.x]++;
            reduce(pqa);
            cnt[one1.x]--;
            one2 = get_top(pqa);
        }
        node two = get_top(pqb);
        if (pqb.empty() || one1.t + one2.t < two.t)
        {
            k -= one1.t;
            ans++;
            cnt[one1.x]++;
            if (mx == 2 && cnt[one1.x] == 1)
            {
                pqa.pp({abs(seg1[one1.x] - seg2[one1.x]), one1.x, 1});
            }
        }
        else
        {   
            ans++;
            pqa.pp(one1);
            k -= min(seg1[two.x], seg2[two.x]);
            cnt[two.x]++;
            pqa.pp({abs(seg1[two.x] - seg2[two.x]), two.x, 1});
            pqb.pop();
        }
    }
    //cout <<"1\n";
    return k < 0 ? 0 : ans;
}
void ddd(vector<ll>& cseg, int nn, ll dist) {
	vis[nn] = true;
	cseg[nn] = dist;
	for (auto [c,w] : graph[nn]) {
		if (!vis[c]) {
			ddd(cseg, c, dist + (ll)w);
		}
	}
}
int max_score(int N, int X, int Y, ll k, vector<int> U, vector<int> V, vector<int> W) {
    graph.clear();
        vis.clear();
        seg1.clear();
        seg2.clear();
    graph.resize(N);
	seg1.resize(N);
	seg2.resize(N);
    //cout <<"1\n";
    for (int i = 0; i < N - 1; i++) {
		graph[U[i]].pb({V[i], W[i]});
		graph[V[i]].pb({U[i], W[i]});
	}
	//travel through "a" values for X
    //cout <<"1\n RTE LMFAO";
    vis.assign(N,false);
	ddd(seg1, X, (ll)0);
	//travel through "a" values for Y
	vis.assign(N,false);
    //cout <<"1\n";
    ddd(seg2, Y, (ll)0);


	//max of b's and a's for X->Y
    //cout <<"1\n";
    return max(greedy(N,2, k, seg1[Y]), greedy(N,1, k, seg1[Y]));
    //return 1;
}