#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
const int mxn = 2e5+5;
vector<pll> g[mxn];
ll d[2][mxn]{0};
int lvl[mxn]{0};
int core[mxn]{0};
multiset<pll> ms;
// Standard DFS to calculate distances from a source node
void dfs(int i, int u, int p) {
for(auto [v, w] : g[u]) {
if(v == p) continue;
d[i][v] = d[i][u] + w;
dfs(i, v, u);
}
}
// Resets global arrays for multiple test cases
void clean(int n) {
for(int i = 0; i < n; i++) {
g[i].clear();
d[0][i] = d[1][i] = lvl[i] = core[i] = 0;
}
}
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
// Build the adjacency list
for(int i = 0; i < N - 1; i++) {
g[U[i]].pb({(ll)V[i], (ll)W[i]});
g[V[i]].pb({(ll)U[i], (ll)W[i]});
}
// Calculate distances from both starting points X and Y
dfs(0, X, X);
dfs(1, Y, Y);
// --- CASE 1: Independent Greedy ---
// Nodes are treated as separate instances for X and Y.
// We just pick the cheapest distances globally until K is exhausted.
ll sum = 0;
int rs1 = 0;
priority_queue<ll, vector<ll>, greater<ll>> pq;
for(int i = 0; i < N; i++) {
pq.push(d[0][i]);
pq.push(d[1][i]);
}
while(!pq.empty() && sum + pq.top() <= K) {
sum += pq.top();
rs1++;
pq.pop();
}
// --- Prep for CASE 2: Overlapping Greedy ---
// Normalize distances so d[0] is distance to nearest source,
// and d[1] is the incremental cost to reach the second level.
for(int i = 0; i < N; i++) {
if(d[0][i] > d[1][i]) swap(d[0][i], d[1][i]);
d[1][i] -= d[0][i];
}
sum = 0;
int rs2 = 0;
ms.clear();
ms.insert({0, -1}); // Sentinel
priority_queue<pll, vector<pll>, greater<pll>> q1, q2;
// Identify the "core" path between X and Y. These nodes MUST be visited.
for(int i = 0; i < N; i++) {
if(d[0][i] + d[1][i] + d[0][i] == d[1][X] + d[0][X]) { // Check if node is on the X-Y path
sum += d[0][i];
rs2++;
lvl[i] = 1;
q1.push({d[1][i], i + 1}); // Add incremental cost to reach level 2
core[i] = 1;
}
}
// Fill queues: q1 for 1-level gains, q2 for 2-level gains at once
for(int i = 0; i < N; i++) {
if(lvl[i] == 0) {
q1.push({d[0][i], -(i + 1)});
q2.push({d[0][i] + d[1][i], i + 1});
}
}
if(sum > K) {
clean(N);
return rs1;
}
// Greedy selection with potential "backtracking" (using multiset ms)
while(!q1.empty() || !q2.empty()) {
// Handle cases where one queue is empty
if(q2.empty()) {
auto [x, i] = q1.top(); q1.pop();
int lv = (i > 0); i = abs(i) - 1;
if(lvl[i] > lv) continue;
if(sum + x > K) { clean(N); return max(rs1, rs2); }
sum += x; rs2++;
if(lvl[i] == 0) { lvl[i] = 1; ms.insert({x, i}); q1.push({d[1][i], i + 1}); }
else if(lvl[i] == 1) { lvl[i] = 2; if(!core[i]) ms.erase({d[0][i], i}); ms.insert({x, i}); }
}
else if(q1.empty()) {
auto [x, i] = q2.top(); q2.pop(); i--;
if(lvl[i] != 0) continue;
if(sum + x > K) { clean(N); return max(rs1, rs2); }
sum += x; rs2 += 2;
lvl[i] = 2; ms.insert({d[1][i], i});
}
// Main greedy logic: compare taking one best node vs taking a pair/level-2 node and removing the most expensive current pick
else if(q1.top().f <= q2.top().f - (--ms.end())->f) {
auto [x, i] = q1.top(); q1.pop();
int lv = (i > 0); i = abs(i) - 1;
if(sum + x > K) { clean(N); return max(rs1, rs2); }
sum += x; rs2++;
if(lvl[i] == 0) { lvl[i] = 1; ms.insert({x, i}); q1.push({d[1][i], i + 1}); }
else if(lvl[i] == 1) { lvl[i] = 2; if(!core[i]) ms.erase({d[0][i], i}); ms.insert({x, i}); }
}
else {
// Replacement logic: take a 2-level jump and undo the least efficient previous move
auto [x, i] = q2.top(); q2.pop(); i--;
if(lvl[i] != 0) continue;
if(sum + x - (--ms.end())->f > K) { clean(N); return max(rs1, rs2); }
sum += x - (--ms.end())->f; rs2++;
auto it = (--ms.end());
// Update the state of the node we "undid" or downgraded
if(lvl[it->s] == 1) {
lvl[it->s] = 0;
q1.push({d[0][it->s], -it->s - 1});
q2.push({d[0][it->s] + d[1][it->s], it->s + 1});
ms.erase(it);
}
else if(lvl[it->s] == 2) {
lvl[it->s] = 1;
q1.push({d[1][it->s], it->s + 1});
if(!core[it->s]) ms.insert({d[0][it->s], it->s});
ms.erase(it);
}
lvl[i] = 2; ms.insert({d[1][i], i});
}
}
clean(N);
return max(rs1, rs2);
}
