#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, 4> CostNodeFrom;
CostNodeFrom plain = {-1,-1,-1,-1};
multiset<CostNodeFrom> prim;
const int LIM = 200000;
vector <PLL> edge[LIM + 5];
bool isInside[LIM + 5][2];
LL curans[LIM + 5];
CostNodeFrom cheap[LIM + 5][2];
ostream& operator<<(ostream &os, CostNodeFrom c) {
	os <<"(" << c[0] << ", " << c[1] << ", " << c[2] << ", " << c[3] <<")";
	return os;
}
 

void updateCheap(int node, LL val, bool isX) {
	//~ cout << "Updating " << endl;
	cheap[node][isX] = plain;
	if(cheap[node][!isX][1] != -1) {
		prim.erase(prim.find(cheap[node][!isX]));
		curans[node] += val;
		cheap[node][!isX][0] = max(0LL, cheap[node][!isX][3] - curans[node]);
		//~ assert(oldCost - curans[node] >= 0);
		//~ cout << cheap[node][!isX] << endl;
		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][0] = isInside[i][1] = 0;
		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][0] = 1;
	isInside[Y][1] = 1;
	LL ans = 2;
	trav(tmp, edge[X]){
		CostNodeFrom nx = {tmp.se, 0, X, tmp.se};
		prim.insert(nx);
		cheap[tmp.fi][1] = nx;
	}
	trav(tmp, edge[Y]) {
		CostNodeFrom nx = {tmp.se, 1, Y, tmp.se};
		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]);
		trav(cur, edge[currentTop[1]]){
			if(isInside[cur.fi][currentTop[2]] ) continue;
			auto addCost = max(currentTop[3] + cur.se - curans[cur.fi], 0LL);
			CostNodeFrom nxCheap = {addCost, cur.fi, currentTop[2], currentTop[3] + cur.se};
			cheap[cur.fi][currentTop[2]] = nxCheap;
			prim.insert(nxCheap);
		}
		K -= currentTop[0];
		ans++;
		isInside[currentTop[1]][currentTop[2]] = 1;
	}
	//~ rep(i,0,n){
		//~ cout << curans[i] << " ";
	//~ }
	//~ cout << endl;
    return ans;
}