#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 p = -1) {
down.push_back(u);
for (auto [v, w] : g[u]) {
if (!spec[v] && v != p) {
collect(v, u);
}
}
}
ll dp[N][2 * N][4];
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) {
vector<ll> 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;
};
vector<ll> 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>>> mn(4, vector<vector<ll>>(v.size()));
vi pc = {0, 1, 1, 2};
for (int x = 0; x < 4; ++x) {
auto f = [&](int node, int x) {
ll val = 0;
if (x == 1) {
val = dx[node];
} else if (x == 3) {
val = max(dx[node], dy[node]);
} else if (x == 2) {
val = dy[node];
}
return val;
};
for (int i = 0; i < v.size(); ++i) {
mn[x][i].assign(2 * n + 1, 1e18);
sort(v[i].begin(), v[i].end(), [&](int a, int b) { return f(a, x) < f(b, x); });
for (int p = 0; p <= v[i].size(); ++p) {
for (int q = 0; q <= 2 * v[i].size(); ++q) {
for (int t = 0; t < 4; ++t) {
dp[p][q][t] = 1e18;
}
}
}
dp[0][__builtin_popcount(x)][x] = f(v[i][0], x);
for (int j = 1; j < v[i].size(); ++j) {
int node = v[i][j];
for (int sum = 0; sum <= 2 * v[i].size(); ++sum) {
for (int s = 0; s < 4; ++s) {
for (int ns = 0; ns <= s; ++ns) {
if ((ns & s) == ns && sum >= pc[ns]) {
ckmin(dp[j][sum][ns], dp[j - 1][sum - pc[ns]][s] + f(node, ns));
}
}
}
}
}
for (int j = 0; j <= 2 * v[i].size(); ++j) {
mn[x][i][j] = 1e18;
for (int s = 0; s < 4; ++s) {
ckmin(mn[x][i][j], dp[v[i].size() - 1][j][s]);
}
}
}
}
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] = dp[0][0][1] = dp[0][0][2] = 0;
int sum = 0;
for (int i = 1; i <= path.size(); ++i) {
sum += 2 * v[i - 1].size();
for (int j = 0; j <= sum; ++j) {
for (int s = 0; s < 3; ++s) {
int val = 0;
if (s == 0) {
val = 1;
} else if (s == 2) {
val = 2;
} else {
if (mid == 0) val = 0;
else val = 3;
}
for (int k = 0; k <= j && k <= 2 * v[i - 1].size(); ++k) {
for (int ls = 0; ls <= s; ++ls) {
ckmin(dp[i][j][s], dp[i - 1][j - k][ls] + mn[val][i - 1][k]);
}
}
}
}
}
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 = 0; i <= n; ++i) {
g[i].clear();
spec[i] = 0;
}
return ans;
}
