#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using pi = pair<int, int>;
using pli = pair<ll, int>;
using vb = vector<bool>;
int N, X, Y; ll K;
vi U, V; vl W;
vvi adj; map<pi, int> weights;
vl compute_distances(int start) {
vl distances(N, 0LL);
vi parent(N, -1);
queue<int> q;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (v == parent[u]) continue;
q.push(v);
distances[v] = distances[u] + weights[{u, v}];
parent[v] = u;
}
}
return distances;
}
void bfs_cap(int maxnodes, vl &tim, vb &vis, vl &xdist, int &seen, ll &cur_sum) {
priority_queue<pli, vector<pli>, greater<pli>> q;
q.push({0LL, X});
while (!q.empty()) {
int u = q.top().second;
ll dist = q.top().first;
q.pop();
if (vis[u]) continue;
if (seen >= maxnodes) break;
vis[u] = true;
seen++;
cur_sum += dist;
tim[u] = dist;
for (int v : adj[u]) {
if (vis[v]) continue;
q.push({xdist[v], v});
}
}
}
void bfs_rem(vl &tim, vb &vis, vl &xdist, vl &ydist, int &seen, ll &cur_sum) {
vb newvis(N, false);
priority_queue<pli, vector<pli>, greater<pli>> q;
q.push({0LL, Y});
while (!q.empty()) {
int u = q.top().second;
ll dist = q.top().first;
q.pop();
if (newvis[u]) continue;
if (cur_sum + dist > K) break;
newvis[u] = true;
seen++;
cur_sum += dist;
tim[u] = dist;
for (int v : adj[u]) {
if (newvis[v]) continue;
ll ndist = ydist[v];
if (vis[v]) ndist = max(0LL, ydist[v] - xdist[v]);
q.push({ndist, v});
}
}
}
int get_reachable(int x_cap, vl &xdist, vl &ydist) {
vl tim(N, 0LL);
vb vis(N, false);
int seen = 0;
ll cur_sum = 0LL;
bfs_cap(x_cap, tim, vis, xdist, seen, cur_sum);
bfs_rem(tim, vis, xdist, ydist, seen, cur_sum);
if (cur_sum > K) return 0;
return seen;
}
int solve() {
vl distX = compute_distances(X), distY = compute_distances(Y);
int lo = 1, hi = N;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int val_mid = get_reachable(mid, distX, distY);
int val_next = get_reachable(mid + 1, distX, distY);
if (val_mid < val_next) {
lo = mid + 1;
} else {
hi = mid;
}
}
return get_reachable(lo, distX, distY);
}
/*
N: number of cities <= 200k
X, Y: 2 cities of interest 0 < X != Y < N
K: maximum allowed sum of closing times <= 10^18
U, V: road[j] = (U[j], V[j])
W: W[j] = length of road[W]
*/
int max_score(int _N, int _X, int _Y, ll _K, vi _U, vi _V, vi _W) {
W.resize(0); weights.clear();
N = _N; X = _X; Y = _Y; K = _K; U = _U; V = _V; for (int i = 0; i < N - 1; i++) W.push_back(ll(_W[i]));
adj.assign(N, vi());
bool line = true;
for (int i = 0; i < N - 1; i++) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
weights[{U[i], V[i]}] = W[i];
weights[{V[i], U[i]}] = W[i];
line = line && max(U[i], V[i]) == min(U[i], V[i]) + 1;
}
int ans = solve();
return ans;
}
