#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
struct BIT
{
int n;
vector<int> ft;
void init(int N)
{
n = N + 5;
ft.assign(n + 5, 0);
}
void add(int pos, int val)
{
for (pos = pos + 1; pos <= n; pos += pos & -pos) ft[pos] += val;
}
int get(int pos, int res = 0)
{
for (pos = pos + 1; pos > 0; pos -= pos & -pos) res += ft[pos];
return res;
}
};
const int MXN = 2e5 + 5;
int n, x, y;
int k;
vector<array<int, 2>> adj[MXN];
int d[2][MXN], p[3][MXN];
vector<int> pt, PT;
int dp[3001][6001];
int in[MXN], IN[MXN];
void dfs(int a, int p, int t)
{
PT.push_back(a);
if (a != p && a == y) pt = PT;
for (const array<int, 2> &v : adj[a])
{
if (v[0] == p) continue;
d[t][v[0]] = d[t][a] + v[1];
dfs(v[0], a, t);
}
PT.pop_back();
}
void getcomp(int a, int p, vector<int> &comp)
{
for (array<int, 2> &v : adj[a])
{
if (v[0] == p || IN[v[0]]) continue;
getcomp(v[0], a, comp);
}
comp.push_back(a);
}
int32_t max_score(int32_t N, int32_t X, int32_t Y, int K, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W)
{
n = N, x = X, y = Y, k = K;
for (int i = 0; i < n; i++)
{
d[0][i] = d[1][i] = 0;
adj[i].clear();
IN[i] = 0;
}
for (int i = 0; i < n - 1; i++)
{
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
dfs(x, x, 0);
dfs(y, y, 1);
int ans = 0;
{
vector<int> v;
for (int i = 0; i < n; i++) v.push_back(min(d[0][i], d[1][i]));
sort(v.begin(), v.end());
int k1 = k;
for (int i = 0; i < n; i++)
{
k1 -= v[i];
if (k1 < 0) break;
ans++;
}
}
if (d[0][y] > 2 * k) return ans;
for (int i = 0; i <= n; i++) for (int j = 0; j <= 2 * n; j++) dp[i][j] = inf;
dp[0][0] = 0;
for (int &i : pt) IN[i] = 1, dp[0][0] += min(d[0][i], d[1][i]);
for (int i = 1; i <= n; i++)
{
int val[3] = {0, min(d[0][i - 1], d[1][i - 1]), max(d[0][i - 1], d[1][i - 1])};
if (IN[i - 1]) val[1] = max(d[0][i - 1], d[1][i - 1]) - min(d[0][i - 1], d[1][i - 1]), val[2] = inf;
for (int j = 0; j <= 2 * n; j++)
{
for (int k = 0; j + k <= 2 * n && k < 3; k++)
{
dp[i][j + k] = min(dp[i][j + k], dp[i - 1][j] + val[k]);
}
}
}
for (int i = 2 * n; i >= 0; i--)
{
if (dp[n][i] <= k) return max(ans, i + (int)pt.size());
}
return ans;
}
