#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }
const int N = 3000 + 7;
vector<pi> g[N];
vi stk, path;
void dfs(int u, int t, int p = -1) {
stk.push_back(u);
if (u == t) path = stk;
for (auto [v, w] : g[u]) {
if (v == p) continue;
dfs(v, t, u);
}
stk.pop_back();
}
bool spec[N];
vi down;
void collect(int u, int d = 0, int p = -1) {
down.push_back(u);
for (auto [v, w] : g[u]) {
if (!spec[v] && v != p) {
collect(v, d + w, u);
}
}
}
ll dp[N][N][3];
int max_score(int n, int x, int y, ll k, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < n - 1; ++i) {
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
path.clear();
dfs(x, y);
for (auto x : path) spec[x] = 1;
auto get_dist = [&](int u) {
vi dist(n, -1);
queue<int> q;
q.push(u);
dist[u] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [v, w] : g[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + w;
q.push(v);
}
}
}
return dist;
};
vi dx = get_dist(x), dy = get_dist(y);
vector<vi> v;
for (auto x : path) {
down.clear();
collect(x);
v.push_back(down);
}
vector<vector<vector<ll>>> pref(3, vector<vector<ll>>(v.size()));
for (int x = 0; x < 3; ++x) {
auto f = [&](int node, int x) {
ll val = 0;
if (x == 0) {
val = dx[node];
} else if (x == 1) {
val = max(dx[node], dy[node]);
} else {
val = dy[node];
}
return val;
};
for (int i = 0; i < v.size(); ++i) {
pref[x][i].assign(v[i].size(), 0);
sort(v[i].begin(), v[i].end(), [&](int a, int b) { return f(a, x) < f(b, x); });
for (int j = 0; j < v[i].size(); ++j) {
int node = v[i][j];
pref[x][i][j] = (j == 0 ? 0 : pref[x][i][j - 1]) + f(node, x);
}
}
}
int ans = 0;
for (int mid : {0, 2}) {
for (int i = 0; i <= path.size(); ++i) {
for (int j = 0; j <= 2 * n; ++j) {
for (int s = 0; s < 3; ++s) {
dp[i][j][s] = 1e18;
}
}
}
dp[0][0][0] = 0;
for (int i = 1; i <= path.size(); ++i) {
for (int j = 0; j <= 2 * n; ++j) {
for (int k = 1; k <= v[i - 1].size(); ++k) {
for (int s = 0; s < 3; ++s) {
int val = (s == 1 ? mid : 1);
if (val * k > j) continue;
for (int ls = 0; ls <= s; ++ls) {
ckmin(dp[i][j][s], dp[i - 1][j - val * k][ls] + (mid == 0 && s == 1 ? 0 : pref[s][i - 1][k - 1]));
}
}
}
}
}
for (int i = 0; i <= 2 * n; ++i) {
for (int s = 0; s < 3; ++s) {
if (dp[path.size()][i][s] <= k) {
ckmax(ans, i);
}
}
}
}
for (int i = 1; i <= n; ++i) {
g[i].clear();
spec[i] = 0;
}
return ans;
}
