#include "closing.h"
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
#define ll long long
vector<pair<int, ll> > graph[200005];
ll distx[200005], disty[200005];
void dfs(int node, int parent, ll* dist)
{
for (int i = 0; i < graph[node].size(); i++) {
int nxt = graph[node][i].first;
if (nxt == parent) continue;
dist[nxt] = dist[node] + graph[node][i].second;
dfs(nxt, node, dist);
}
}
ll f[3005][6005];
const ll inf = 1000000000000000000LL;
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
for (int i = 0; i < N - 1; i++) {
graph[U[i]].push_back(make_pair(V[i], (ll)W[i]));
graph[V[i]].push_back(make_pair(U[i], (ll)W[i]));
}
dfs(X, -1, distx);
dfs(Y, -1, disty);
vector<ll> all_dists;
for (int i = 0; i < N; i++) {
all_dists.push_back(distx[i]);
all_dists.push_back(disty[i]);
}
sort(all_dists.begin(), all_dists.end());
int ans = 0;
ll curtot = 0;
for (int i = 0; i < 2*N; i++) {
curtot += all_dists[i];
if (curtot <= K) ans = i + 1;
}
if (N <= 3000) {
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= 2 * N + 3; j++) f[i][j] = inf;
}
f[0][0] = 0;
for (int i = 0; i < N; i++) {
if (distx[i] + disty[i] == distx[Y]) {
for (int j = 0; j <= 2 * i; j++) {
f[i+1][j+1] = min(f[i+1][j+1], f[i][j] + min(distx[i], disty[i]));
f[i+1][j+2] = min(f[i+1][j+2], f[i][j] + max(distx[i], disty[i]));
}
} else {
for (int j = 0; j <= 2 * i; j++) {
f[i+1][j] = min(f[i+1][j], f[i][j]);
f[i+1][j+1] = min(f[i+1][j+1], f[i][j] + min(distx[i], disty[i]));
f[i+1][j+2] = min(f[i+1][j+2], f[i][j] + max(distx[i], disty[i]));
}
}
}
for (int i = 0; i <= 2 * N; i++) {
if (f[N][i] <= K) {
ans = max(ans, i);
}
}
}
for (int i = 0; i < N; i++) {
graph[i].clear();
distx[i] = disty[i] = 0;
}
return ans;
}
