#include "closing.h"
#include <bits/stdc++.h>
#define maxn 200005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int n, x, y; int64_t k;
int64_t dp[2005][2005];
int64_t disX[2005], disY[2005];
int64_t cost_level_one[2005], cost_level_two[2005];
vector<ii> adj[2005];
void calcdisX() {
function<void(int, int)> dfs = [&](int u, int dad) {
for (auto [v, l] : adj[u])
if (v != dad) {
disX[v] = disX[u] + l;
dfs(v, u);
}
};
disX[x] = 0;
dfs(x, -1);
}
void calcdisY() {
function<void(int, int)> dfs = [&](int u, int dad) {
for (auto [v, l] : adj[u])
if (v != dad) {
disY[v] = disY[u] + l;
dfs(v, u);
}
};
disY[y] = 0;
dfs(y, -1);
}
int solve() {
calcdisX(); calcdisY();
for (int i = 0; i < n; i++)
cost_level_two[i] = max(disX[i], disY[i]) - (cost_level_one[i] = min(disX[i], disY[i]));
for (int i = 1; i <= n; i++) dp[n][i] = LLONG_MAX/100;
for (int i = n-1; i >= 0; i--) {
for (int j = 1; j <= n; j++) dp[i][j] = dp[i+1][j];
for (int j = 0; j <= n; j++) {
if (j+1 <= n) dp[i][j+1] = min(dp[i][j+1], dp[i+1][j] + cost_level_one[i]);
if (j+2 <= n) dp[i][j+2] = min(dp[i][j+2], dp[i+1][j] + cost_level_one[i] + cost_level_two[i]);
}
}
int ans = 0;
for (int i = 0; i <= n; i++) if (dp[0][i] <= k) ans = i;
return ans;
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
n = N; x = X; y = Y; k = K;
for (int i = 0; i < N-1; i++) {
adj[U[i]].emplace_back(V[i], W[i]);
adj[V[i]].emplace_back(U[i], W[i]);
}
int ans = solve();
for (int i = 0; i < N; i++) adj[i].clear();
for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) dp[i][j] = 0;
return ans;
}
