#include "closing.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i = a;i < b;i++)
#define trav(nx, v) for(auto &nx : v)
#define all(a) begin(a), end(a)
#define sz(v) (int) v.size()

int n;
typedef array<LL, 3> CostNodeFrom;
CostNodeFrom plain = {-1,-1,-1};
multiset<CostNodeFrom> prim;
const int LIM = 200000;
vector <PLL> edge[LIM + 5];
set <int> isInside[LIM + 5];
LL curans[LIM + 5];
CostNodeFrom cheap[LIM + 5][2];

void updateCheap(int node, LL val, bool isX) {
	//~ cout << "Updating " << endl;
	cheap[node][isX] = plain;
	if(cheap[node][!isX][1] != -1) {
		//~ cout << "Replacing " << endl;
		prim.erase(prim.find(cheap[node][!isX]));
		LL oldCost = cheap[node][!isX][0] + curans[node];
		curans[node] += val;
		cheap[node][!isX][0] = oldCost - curans[node];
		prim.insert(cheap[node][!isX]);
	} else {
		curans[node] = val;
	}
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W){
	n = N;
	rep(i,0,N) {
		edge[i].clear();
		isInside[i].clear();
		curans[i] = 0;
		cheap[i][0] = cheap[i][1] = plain;
	}
	//~ cout << "Here " << U[0] << " " << V[0] << ""  << W[0] << endl;
	prim.clear();
	rep(i,0,N - 1){
		if(W[i] > K) continue;
		//~ cout << U[i] << " " << V[i] << endl;
		edge[U[i]].emplace_back(V[i], W[i]);
		edge[V[i]].emplace_back(U[i], W[i]);
		
	}
	isInside[X].insert(X);
	isInside[Y].insert(Y);
	LL ans = 2;
	trav(tmp, edge[X]){
		CostNodeFrom nx = {tmp.se, tmp.fi, X};
		prim.insert(nx);
		cheap[tmp.fi][1] = nx;
	}
	trav(tmp, edge[Y]) {
		CostNodeFrom nx = {tmp.se, tmp.fi, Y};
		prim.insert(nx);
		cheap[tmp.fi][0] = nx;
	}
	while(sz(prim)){
		auto currentTop = *prim.begin();
		//~ cout << "here K = " << K << " relaxing node " << currentTop[1] << " with cost " << currentTop[0] << " from node " << currentTop[2] << endl;
		prim.erase(prim.begin());
		if(K < currentTop[0]) break;
		updateCheap(currentTop[1], currentTop[0], currentTop[2] == X);
		trav(cur, edge[currentTop[1]]){
			if(isInside[cur.fi].count(currentTop[2])) continue;
			prim.insert({cur.se + currentTop[0] - curans[cur.fi], cur.fi, currentTop[2]});
		}
		K -= currentTop[0];
		ans++;
		isInside[currentTop[1]].insert(currentTop[2]);
	}
	//~ rep(i,0,n){
		//~ cout << curans[i] << " ";
	//~ }
	//~ cout << endl;
    return ans;
}