#include "closing.h"
#include <bits/stdc++.h>
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 ((ll) 1 << 30)
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
using namespace std;
vector<vector<pair<ll, ll>>> adj;
vector<ll> memo;
struct TPos {
ll i, wth = -INF64, from;
string toString() {
return to_string(i) + ":" + to_string(wth) + ":" + to_string(from);
}
};
bool operator < (const TPos& a, const TPos& b) {
return (a.wth - memo[a.i] > b.wth - memo[b.i]);
}
bool operator == (const TPos& a, const TPos& b) {
return (a.i == b.i && a.from == b.from && a.wth == b.wth);
}
vector<TPos> fut;
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
adj.clear();
adj.resize(N);
memo.clear();
memo.resize(N);
fut.clear();
fut.resize(N);
range(i, 0, N - 1){
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
pqueue<TPos> pq;
pq.push({X, 0, X});
fut[X] = {X, 0, X};
pq.push({Y, 0, Y});
fut[Y] = {Y, 0, Y};
ll ans = 0;
ll sum = 0;
TPos t;
while (!pq.empty()) {
t = pq.top(); pq.pop();
if (fut[t.i].wth == -INF64) continue;
if (t == fut[t.i]) fut[t.i].wth = -INF64;
ll dif = t.wth - memo[t.i];
if (sum + dif > K) break;
// cout << t.toString() << " | ";
memo[t.i] = t.wth;
if (fut[t.i].wth != -INF64)
pq.push(fut[t.i]);
for (pair<ll, ll> a : adj[t.i]) {
if (a.first != t.from) {
pq.push({a.first, t.wth + a.second, t.i});
if (t.wth + a.second >= fut[a.first].wth) {
fut[a.first] = {a.first, t.wth + a.second, t.i};
}
}
}
// range(i, 0, N) cout << "[ " << fut[i].toString() << " ] ";
// cout << '\n';
ans++;
sum += dif;
}
// cout << "----------------\n";
return ans;
}
