#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;
ll k1, k2, ans, ans1, ans2;
vector<vector<pair<ll, ll>>> adj;
vector<ll> distX, distY;
vector<pair<ll, ll>> cost;
pqueue<pair<ll, ll>> pqa, pq1, pq2, pq3;
void dfs_x (ll i, ll cnt, ll from) {
distX[i] = cnt;
for (auto k : adj[i]) {
if (k.first != from) {
dfs_x(k.first, cnt + k.second, i);
}
}
}
void dfs_y (ll i, ll cnt, ll from) {
distY[i] = cnt;
for (auto k : adj[i]) {
if (k.first != from) {
dfs_y(k.first, cnt + k.second, i);
}
}
cost[i].first = min(distX[i], distY[i]);
cost[i].second = max(distX[i], distY[i]) - cost[i].first;
}
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);
distX.clear();
distX.resize(N);
distY.clear();
distY.resize(N);
cost.clear();
cost.resize(N);
while (!pqa.empty()) pqa.pop();
while (!pq1.empty()) pq1.pop();
while (!pq2.empty()) pq2.pop();
while (!pq3.empty()) pq3.pop();
range(i, 0, N - 1){
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
k1 = k2 = K;
ans = ans1 = ans2 = 0;
dfs_x(X, 0, X);
dfs_y(Y, 0, Y);
vector<ll> memo (N);
range (i, 0, N) {
pqa.push({-cost[i].first, i});
// TYPE 2: BELONGS TO THE PATH X => Y
if (2 * cost[i].first + cost[i].second == distX[Y]) {
k2 -= cost[i].first;
ans2++;
pq1.push({-cost[i].second, i});
memo[i]++;
// cout << "[ " << i << " ] ";
}
// TYPE 1: lv1 >= lv2
else if (cost[i].first >= cost[i].second) {
pq3.push({-cost[i].first, i});
pq2.push({-(cost[i].first + cost[i].second), i});
}
// TYPE 0: DEFAULT
else {
pq1.push({-cost[i].first, i});
pq1.push({-cost[i].second, i});
}
}
while (!pqa.empty() && k1 + pqa.top().first >= 0) {
k1 += pqa.top().first;
pqa.pop();
ans1++;
}
ans = ans1;
pair<ll, ll> t;
if (k2 >= 0) {
while (!pq2.empty() && k2 + pq2.top().first >= 0) {
if (pq1.size() < 2) {
k2 += pq2.top().first;
if (k2 >= 0) {
memo[pq2.top().second] = 2;
ans2 += 2;
// cout << "[ " << pq2.top().second << ", lv2 ] ";
pq2.pop();
continue;
}
}
t = pq1.top(); pq1.pop();
if (pq1.top().first + t.first > pq2.top().first && k2 + t.first >= 0) {
k2 += t.first;
ans2++;
// cout << "[ " << t.second << " ] ";
memo[t.second]++;
}
else if (pq2.top().first + k2 >= 0) {
k2 += pq2.top().first;
pq1.push(t);
ans2 += 2;
// cout << "[ " << pq2.top().second << ", lv2 ] ";
memo[pq2.top().second] = 2;
pq2.pop();
}
}
while (!pq1.empty() && k2 + pq1.top().first >= 0) {
k2 += pq1.top().first;
ans2++;
memo[pq1.top().second]++;
// cout << "[ " << pq1.top().second << " ] ";
pq1.pop();
}
while (!pq3.empty() && memo[pq3.top().second] != 0) pq3.pop();
if (!pq3.empty() && pq3.top().first + k2 >= 0) ans2++;
ans = max(ans, ans2);
}
cout << '\n';
return ans;
}
