#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
vector<pll> T[202020];
ll X[202020], Y[202020];
int n; ll l;
void dfs(int u, int p, ll *X) {
for (auto &[v, w]: T[u]) if (v != p) {
X[v] = X[u] + w;
dfs(v, u, X);
}
}
int solve1(ll k) {
vector<ll> V;
int i;
for (i = 0; i < n; i++) {
V.push_back(X[i]);
V.push_back(Y[i]);
}
sort(V.begin(), V.end());
for (i = 0; i < n + n; i++) {
k -= V[i];
if (k < 0) break;
}
return i;
}
ll D[6060];
int solve2(ll k) {
priority_queue<pll> P01, P02, P10, P12, P21;
vector<ll> C(n, 0);
int i;
for (i = 0; i < n; i++) {
if (X[i] > Y[i]) swap(X[i], Y[i]);
if (X[i] + Y[i] == l) {
k -= X[i]; Y[i] -= X[i]; X[i] = 0;
}
Y[i] -= X[i];
P01.emplace(-X[i], i);
P02.emplace(-X[i] - Y[i], i);
}
if (k < 0) return 0;
for (i = 0; i < n + n; i++) {
ll m = -1e18; int f;
for (; !P01.empty() && C[P01.top().second] != 0; P01.pop());
for (; !P02.empty() && C[P02.top().second] != 0; P02.pop());
for (; !P10.empty() && C[P10.top().second] != 1; P10.pop());
for (; !P12.empty() && C[P12.top().second] != 1; P12.pop());
for (; !P21.empty() && C[P21.top().second] != 2; P21.pop());
if (!P01.empty()) {
auto [t, _] = P01.top();
if (m < t) m = t, f = 1;
}
if (!P12.empty()) {
auto [t, _] = P12.top();
if (m < t) m = t, f = 2;
}
if (!P10.empty() && !P02.empty()) {
auto [t1, _] = P10.top();
auto [t2, __] = P02.top();
ll t = t1 + t2;
if (m < t) m = t, f = 3;
}
if (!P21.empty() && !P02.empty()) {
auto [t1, _] = P21.top();
auto [t2, __] = P02.top();
ll t = t1 + t2;
if (m < t) m = t, f = 4;
}
k += m;
if (k < 0) break;
if (f == 1) {
auto [t, j] = P01.top(); P01.pop();
P10.emplace(X[j], j);
P12.emplace(-Y[j], j);
C[j] = 1;
} else if (f == 2) {
auto [t, j] = P12.top(); P12.pop();
P21.emplace(Y[j], j);
C[j] = 2;
} else if (f == 3) {
auto [t1, j1] = P10.top(); P10.pop();
P01.emplace(-X[j1], j1);
P02.emplace(-X[j1] - Y[j1], j1);
C[j1] = 0;
auto [t2, j2] = P02.top(); P02.pop();
C[j2] = 2;
} else if (f == 4) {
auto [t1, j1] = P21.top(); P21.pop();
P10.emplace(X[j1], j1);
P12.emplace(-Y[j1], j1);
C[j1] = 1;
auto [t2, j2] = P02.top(); P02.pop();
P21.emplace(Y[j2], j2);
C[j2] = 2;
}
}
return i;
}
int max_score(int n, int x, int y, ll k, vector<int> U, vector<int> V, vector<int> W) {
::n = n;
int i;
for (i = 0; i < n; i++) {
T[i].clear();
}
for (i = 0; i < n - 1; i++) {
T[U[i]].emplace_back(V[i], W[i]);
T[V[i]].emplace_back(U[i], W[i]);
}
X[x] = Y[y] = 0;
dfs(x, x, X); dfs(y, y, Y);
l = X[y];
int a = solve1(k);
a = max(a, solve2(k));
return a;
}
