#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define pb push_back
#define eb emplace_back
int to[200005];
ll distX[200005], distY[200005], distX_copy[200005], distY_copy[200005];
vector<ii> adj[200005];
vector<ll> vec_0[200005], vec_1[200005], vec_2[200005];
void get_dist(int u, ll dist[], int e = -1) {
for (auto [v, w] : adj[u]) if (v != e) {
dist[v] = dist[u] + w;
get_dist(v, dist, u);
}
}
bool init(int u, int Y, int e = -1) {
if (u == Y) {
return 1;
}
for (auto [v, _] : adj[u]) if (v != e) {
if (init(v, Y, u)) {
to[u] = v;
return 1;
}
}
return 0;
}
void dp(int u, int e = -1) {
vec_0[u].pb(distX[u]);
vec_1[u].pb((ll)2e18);
vec_1[u].pb(max(distX[u], distY[u]));
vec_2[u].pb(distY[u]);
if (to[u] != -1) {
for (auto [v, _] : adj[u]) if (v != e) {
dp(v, u);
vector<ll> new_vec_0(vec_0[u].size() + vec_1[v].size() - 1, (ll)2e18);
for (int i = 0; i < (int)vec_0[u].size(); i++) {
for (int j = 0; j < (int)vec_1[v].size(); j++) {
ll oth = (v == to[u] ? min(j < (int)vec_0[v].size() ? vec_0[v][j] : (ll)2e18, vec_1[v][j]) : (j < (int)vec_0[v].size() ? vec_0[v][j] : (ll)2e18));
new_vec_0[i + j] = min(new_vec_0[i + j], vec_0[u][i] + oth);
}
}
swap(vec_0[u], new_vec_0);
vector<ll> new_vec_1(vec_1[u].size() + vec_1[v].size() - 1, (ll)2e18);
for (int i = 0; i < (int)vec_1[u].size(); i++) {
for (int j = 0; j < (int)vec_1[v].size(); j++) {
ll oth = (v == to[u] && j < (int)vec_2[v].size() ? min(vec_1[v][j], vec_2[v][j]) : vec_1[v][j]);
new_vec_1[i + j] = min(new_vec_1[i + j], vec_1[u][i] + oth);
}
}
swap(vec_1[u], new_vec_1);
vector<ll> new_vec_2(vec_2[u].size() + vec_2[v].size() - 1, (ll)2e18);
for (int i = 0; i < (int)vec_2[u].size(); i++) {
for (int j = 0; j < (int)vec_2[v].size(); j++) {
new_vec_2[i + j] = min(new_vec_2[i + j], vec_2[u][i] + vec_2[v][j]);
}
}
swap(vec_2[u], new_vec_2);
}
} else {
for (auto [v, _] : adj[u]) if (v != e) {
dp(v, u);
vector<ll> new_vec_0(vec_0[u].size() + vec_0[v].size() - 1, (ll)2e18);
for (int i = 0; i < (int)vec_0[u].size(); i++) {
for (int j = 0; j < (int)vec_0[v].size(); j++) {
new_vec_0[i + j] = min(new_vec_0[i + j], vec_0[u][i] + vec_0[v][j]);
}
}
swap(vec_0[u], new_vec_0);
vector<ll> new_vec_1(vec_1[u].size() + vec_1[v].size() - 1, (ll)2e18);
for (int i = 0; i < (int)vec_1[u].size(); i++) {
for (int j = 0; j < (int)vec_1[v].size(); j++) {
ll oth;
if (j < (int)vec_0[v].size()) {
oth = min({vec_1[v][j], vec_0[v][j], vec_2[v][j]});
} else {
oth = vec_1[v][j];
}
new_vec_1[i + j] = min(new_vec_1[i + j], vec_1[u][i] + oth);
}
}
swap(vec_1[u], new_vec_1);
vector<ll> new_vec_2(vec_2[u].size() + vec_2[v].size() - 1, (ll)2e18);
for (int i = 0; i < (int)vec_2[u].size(); i++) {
for (int j = 0; j < (int)vec_2[v].size(); j++) {
new_vec_2[i + j] = min(new_vec_2[i + j], vec_2[u][i] + vec_2[v][j]);
}
}
swap(vec_2[u], new_vec_2);
}
}
vec_0[u].insert(vec_0[u].begin(), 0);
vec_1[u].insert(vec_1[u].begin(), 0);
vec_2[u].insert(vec_2[u].begin(), 0);
//~ cout << "@ " << u << ":\n";
//~ for (auto i : vec_0[u]) {
//~ cout << i << ' ';
//~ }
//~ cout << '\n';
//~ for (auto i : vec_1[u]) {
//~ cout << i << ' ';
//~ }
//~ cout << '\n';
//~ for (auto i : vec_2[u]) {
//~ cout << i << ' ';
//~ }
//~ cout << '\n';
}
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
int ans = -1;
for (int i = 0; i < N - 1; i++) {
adj[U[i]].eb(V[i], W[i]);
adj[V[i]].eb(U[i], W[i]);
}
get_dist(X, distX);
get_dist(Y, distY);
copy(distX, distX + N, distX_copy);
copy(distY, distY + N, distY_copy);
sort(distX_copy, distX_copy + N);
sort(distY_copy, distY_copy + N);
for (int i = 1; i < N; i++) {
distY_copy[i] += distY_copy[i - 1];
}
ll rs = 0;
for (int i = 0; i < N; i++) {
rs += distX_copy[i];
if (rs > K) {
break;
}
auto it = upper_bound(distY_copy, distY_copy + N, K - rs);
ans = max(ans, i + 1 + (int)(it - distY_copy));
}
fill(to, to + N, -1);
init(X, Y);
dp(X);
assert((int)vec_1[X].size() == 2 * N + 1);
for (int i = 0; i <= 2 * N; i++) {
if ((i < (int)vec_0[X].size() && vec_0[X][i] <= K) || vec_1[X][i] <= K) {
ans = max(ans, i);
}
}
assert(ans != -1);
for (int i = 0; i < N; i++) {
adj[i].clear();
vec_0[i].clear();
vec_1[i].clear();
vec_2[i].clear();
distX[i] = distY[i] = to[i] = 0;
}
return ans;
}
