#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 fixHeuristics(int node){
	//~ cout << "Heur " << node << endl;
	auto average = (cheap[node][0][0] + cheap[node][1][0]) / 4;
	//~ cout << average << endl;
	prim.erase(prim.find(cheap[node][0]));
	prim.erase(prim.find(cheap[node][1]));
	cheap[node][0][0] = average;
	cheap[node][1][0] = average;
	prim.insert(cheap[node][0]);
	prim.insert(cheap[node][1]);
} 

void updateCheap(int node, LL val, bool isY) {
	//~ cout << "Updating " << endl;
	cheap[node][isY] = plain;
	if(cheap[node][!isY][1] != -1) {
		prim.erase(prim.find(cheap[node][!isY]));
		curans[node] += val;
		cheap[node][!isY][0] = max(0LL, cheap[node][!isY][3] - curans[node]);
		prim.insert(cheap[node][!isY]);
	} 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){
	//~ cout << LLONG_MAX << endl;
	K *= 4;
	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){
		auto tmp = 4LL * W[i];
		if(tmp > K) continue;
		//~ cout << U[i] << " " << V[i] << endl;
		edge[U[i]].emplace_back(V[i], tmp);
		edge[V[i]].emplace_back(U[i], tmp);
		
	}
	isInside[X][0] = 1;
	isInside[Y][1] = 1;
	LL ans = 2;
	trav(tmp, edge[X]){
		CostNodeFrom nx = {tmp.se, tmp.fi, 0, tmp.se};
		prim.insert(nx);
		cheap[tmp.fi][0] = nx;
	}
	trav(tmp, edge[Y]) {
		CostNodeFrom nx = {tmp.se, tmp.fi, 1, tmp.se};
		prim.insert(nx);
		cheap[tmp.fi][1] = nx;
		if(cheap[tmp.fi][1][0] != -1){
			fixHeuristics(tmp.fi);
		}
	}
	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());
		auto realCost = max(0LL, currentTop[3] - curans[currentTop[1]]);
		if(K < realCost) continue;
		updateCheap(currentTop[1], realCost, 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);
			// Add heuristics
			if(cheap[cur.fi][!currentTop[2]][1] != -1){
				fixHeuristics(cur.fi);
			}
		}
		K -= realCost;
		ans++;
		isInside[currentTop[1]][currentTop[2]] = 1;
	}
	//~ rep(i,0,n){
		//~ cout << curans[i] / 4 << " ";
	//~ }
	//~ cout << endl;
    return ans;
}