#include <bits/stdc++.h>
using namespace std;
#define ll long long
#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);
    }
};

void ddd(vector<ll>& cseg, int node, ll dist) {
	vis[node] = true;
	cseg[node] = dist;
	for (auto [c, w] : graph[node]) {
		if (!vis[c]) {
			ddd(cseg, c, dist + w);
		}
	}
}

int greedy(int mx, ll k, ll mdist) {
	int N = graph.size(), ans = 0;
	vector<int> cnt(N, 0);
	priority_queue<node, vector<node>, greater<node>> pqa, pqb;

	for (int i = 0; i < N-1; i++) {
		if (mx == 2 && seg1[i] + seg2[i] == mdist) {
			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) {
				pqb.pp({max(seg1[i], seg2[i]), i , 0});
			}
		}
	}

	auto get_top = [](priority_queue<node, vector<node>, greater<node>>& pq) -> node {
        return pq.empty() ? node{(ll)1e18, 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();
        }
    };

    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 {
            pqa.pp(one1);
            k -= min(seg1[two.x], seg2[two.x]);
            ans++;
            cnt[two.x]++;
            pqa.pp({abs(seg1[two.x] - seg2[two.x]), two.x, 1});
            pqb.pop();
        }
    }
    return k < 0 ? 0 : ans;
}

int max_score(int N, int X, int Y, ll k, vector<int> U, vector<int> V, vector<int> W) {
    graph.assign(N , vector<pair<int, ll>>());
	vis.assign(N , false);
	seg1.assign(N , 0);
	seg2.assign(N , 0);

    for (int i = 0; i < N - 1; i++) {
		graph[U[i]].pb({V[i], W[i]});
		graph[V[i]].pb({U[i], W[i]});
	}

	ddd(seg1, X, 0);
	vis.assign(N, false);
	ddd(seg2, Y, 0);

    return max(greedy(2, k, seg1[Y]), greedy(1, k, seg1[Y]));
}