#include "closing.h"
#include "bits/stdc++.h"
using namespace std;
#define vec vector
int max_score(int N, int X, int Y, long long K, vec<int> U, vec<int> V,
vec<int> W) {
vec<vec<pair<int, int>>> adj(N);
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]});
}
auto dijkstra = [&](int src) {
const long long INF = LLONG_MAX / 4;
vec<long long> dist(N, INF);
dist[src] = 0;
priority_queue<pair<long long, int>, vec<pair<long long, int>>,
greater<pair<long long, int>>>
pq;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u])
continue;
for (auto &e : adj[u]) {
int v = e.first;
long long w = e.second;
if (dist[v] > d + w) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
return dist;
};
vec<long long> dx = dijkstra(X);
vec<long long> dy = dijkstra(Y);
vec<long long> dist(N);
for (int i = 0; i < N; ++i) {
dist[i] = min(dx[i], dy[i]);
}
sort(dist.begin(), dist.end());
long long used = 0;
int cnt = 0;
for (auto d : dist) {
if (used + d > K)
break;
used += d;
++cnt;
}
return cnt;
}
