// Source: https://usaco.guide/general/io

#include "closing.h"
#include <bits/stdc++.h>

// #define int long long
#define double long double

#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define edge pair<int, int>

using namespace std;

vector<vector<edge>> adj;
vector<int> psum1, psum2;

int NO1, NO2;

void genshit(int c, int p, int flag) {
	if (p != -1 && flag == 0 && c == NO1) {
		return;
	}

	if (p != -1 && flag == 1 && c == NO2) {
		return;
	}

	for (auto n : adj[c]) {
		if (n.first != p) {
			if (flag == 0) {
				psum1[n.first] = psum1[c] + n.second;
			} else {
				psum2[n.first] = psum2[c] + n.second;
			}

			genshit(n.first, c, flag);
		}
	}
}

struct cmp {
	bool operator()(const array<int, 3> &x, const array<int, 3> &y) const { 
		return x[0] > y[0];
	}
};

struct cmp2 {
	bool operator()(const array<int, 3> &x, const array<int, 3> &y) const { 
		return x[0] < y[0];
	}
};

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
	adj.resize(N); psum1.resize(N); psum2.resize(N); NO1 = X, NO2 = Y;

	for (int i = 0; i < N; i++) {
		adj[i].clear(); psum1[i] = psum2[i] = 0;
	}

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

	// gen psum
	genshit(X, -1, 0); genshit(Y, -1, 1);

	// do the cardboard box thing
	vector<int> a(N), b(N);

	for (int i = 0; i < N; i++) {
		a[i] = min(psum1[i], psum2[i]);
		b[i] = max(psum1[i], psum2[i]);

		// cout << psum1[i] << " " << psum2[i] << "\n";
		// cout << a[i] << " " << b[i] << "\n";
	}

	vector<int> status(N, 0); // 0 = nothing, 1 = one only, 2 = both

	// {cost, vertex, index}
	priority_queue<array<int, 3>, vector<array<int, 3>>, cmp> pq;

	vector<array<int, 3>> trust;

	for (int i = 0; i < N; i++) {
		trust.push_back({a[i], i, 0});
	}

	int ans = 0; int ct = 0;
	
	sort(all(trust), cmp2());

	while (ans <= K) {
		if (ct == N) {
			return ct;
		}

		if (ans + trust[ct][0] <= K) {
			ans += trust[ct][0]; status[trust[ct][1]]++;
			pq.push({b[trust[ct][1]] - a[trust[ct][1]], trust[ct][1], 1}); ct++;
		} else {
			break;
		}
	}

	while (!pq.empty()) {
		auto t = pq.top(); pq.pop();

		bool fin = true;

		if (ans + t[0] <= K) {
			// check if all adj are activated
			for (auto n : adj[t[1]]) {
				if (!status[n.first]) { 
					fin = false;
				}
			}

			if (fin) {
				ans += t[0]; status[t[1]]++; ct++;
			}
		}
	}

	return ct;
}