#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
const int MXN = 2e5 + 5;
int n, x, y;
long long k;
vector<array<long long, 2>> adj[MXN];
long long d[2][MXN], p[2][MXN];
void dfs(int a, int p, int t)
{
for (const array<long long, 2> &v : adj[a])
{
if (v[0] == p) continue;
d[t][v[0]] = d[t][a] + v[1];
dfs(v[0], a, t);
}
}
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; i++)
{
d[0][i] = d[1][i] = 0;
adj[i].clear();
}
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<long long> v;
for (int i = 0; i < n; i++) v.push_back(min(d[0][i], d[1][i]));
sort(v.begin(), v.end());
long long k1 = k;
for (int i = 0; i < n; i++)
{
k1 -= v[i];
if (k1 < 0) break;
ans++;
}
}
for (int j = 0; j < 2; j++)
{
for (int i = 0; i < N; i++)
{
p[j][i] = (i ? p[j][i - 1] : 0) + d[j][i];
}
}
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
if (max(i, X) > min(j, Y)) continue;
long long k1 = k;
for (int k = i; k <= j; k++) k1 -= max(d[0][k], d[1][k]);
for (int k = X; k < i; k++) k1 -= d[0][k];
for (int k = j + 1; k <= Y; k++) k1 -= d[1][k];
if (k1 < 0) continue;
int res = max(j, Y) - min(i, X) + 1 + (j - i + 1);
vector<long long> v;
for (int k = 0; k < min(i, X); k++) v.push_back(d[0][k]);
for (int k = max(j, Y) + 1; k < n; k++) v.push_back(d[1][k]);
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++)
{
k1 -= v[i];
if (k1 < 0) break;
res++;
}
ans = max(ans, res);
}
}
return ans;
}
