#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ll = long long;
using ii = pair<int, int>;
const ll INF = 1e18;
const int MAX_N = 2e5 + 9;
vector<ii> adj[MAX_N];
pair<ll, ll> val[MAX_N];
int n;
void dfs(int u, vector<ll> &dist, int p = -1, ll d = 0) {
dist[u] = d;
for (auto [v, w] : adj[u]) {
if (v != p) dfs(v, dist, u, d + w);
}
}
int non_overlaping(ll K) {
vector<ll> v(n);
for (int i = 0; i < n; i++) {
v[i] = val[i].first;
}
sort(all(v));
int ans = 0;
for (int i = 0; i < n; i++) {
if (v[i] <= K) {
K -= v[i];
ans++;
}
}
return ans;
}
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
n = N;
for (int i = 0; i < n; i++) adj[i].clear();
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]);
}
vector<ll> distToX(n), distToY(n);
dfs(X, distToX), dfs(Y, distToY);
bool flag = false;
for (int i = 0; i < n; i++) {
val[i] = minmax(distToX[i], distToY[i]);
if (val[i].second <= K) flag = true;
}
if (!flag) return non_overlaping(K);
vector<bool> path(n, false);
path[Y] = true;
int u = Y;
while (u != X) {
for (auto [v, w] : adj[u]) {
if (distToX[v] + w == distToX[u]) {
u = v;
break;
}
}
path[u] = true;
}
vector<ll> prevDP(2 * n + 1, INF);
prevDP[0] = 0;
for (int i = 0; i < n; i++) {
vector<ll> currDP(2 * n + 1, INF);
if (!path[i]) currDP = prevDP;
for (int j = 1; j <= 2 * n; j++) {
currDP[j] = min(currDP[j], prevDP[j - 1] + val[i].first);
}
for (int j = 2; j <= 2 * n; j++) {
currDP[j] = min(currDP[j], prevDP[j - 2] + val[i].second);
}
prevDP = currDP;
}
for (int i = 2 * n; i >= 0; i--) {
if (prevDP[i] <= K) return max(i, non_overlaping(K));
}
return non_overlaping(K);
}
