#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
#define ll long long
const int mxn = 3010;
vector<pair<ll, ll>> g[mxn];
ll dist[mxn][2];
void dfs(int node, int type) {
queue<pair<ll, ll>> q;
q.push({0, node});
dist[node][type] = 0;
while (q.size()) {
auto top = q.front();
q.pop();
ll D = top.first, cur = top.second;
for (auto x : g[cur]) {
ll to = x.first, weight = x.second;
ll newD = D + weight;
if (newD < dist[to][type]) {
dist[to][type] = newD;
q.push({newD, to});
}
}
}
}
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; i++) dist[i][0] = dist[i][1] = 1e15, g[i].clear();
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]});
}
dfs(X, 0);
dfs(Y, 1);
vector<ll> v;
for (int i = 0; i < N; i++) {
v.push_back(min(dist[i][0], dist[i][1]));
}
sort(v.begin(), v.end());
ll sum = 0, ans1 = 0;
for (int i = 0; i < N; i++) {
sum += v[i];
if (sum > K) break;
ans1++;
}
ll ans2 = 0;
sum = 0;
for (int i = 0; i < N; i++) {
if (dist[Y][0] == dist[i][0] + dist[i][1]) {
sum += min(dist[i][0], dist[i][1]);
ans2++;
}
}
ll MX = 2 * N + 10;
ll dp[MX];
for (int i = 0; i < MX; i++) dp[i] = 1e15;
dp[ans2] = sum;
for (int i = 0; i < N; i++) {
ll mn = min(dist[i][0], dist[i][1]), mx = max(dist[i][0], dist[i][1]);
if (dist[Y][0] == dist[i][0] + dist[i][1]) {
mn = dist[Y][0] - 2 * mn, mx = 1e15;
}
for (int j = 2 * N; j >= 0; j--) {
ll res = dp[j];
if (j - 1 >= 0) res = min(res, dp[j - 1] + mn);
if (j - 2 >= 0) res = min(res, dp[j - 2] + mx);
dp[j] = res;
}
}
ans2 = 0;
for (int j = 2 * N; j >= 0; j--) {
if (dp[j] <= K) {
ans2 = j;
break;
}
}
return max(ans1, ans2);
}
