#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>;
int N, X, Y; ll K;
vi U, V; vl W;
vvi adj;
vi compute_distances(int start) {
vi distances(N, 0);
vi parent(N, -1);
queue<int> q;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int eid : adj[u]) {
int v = U[eid] == u ? V[eid] : U[eid];
if (v == parent[u]) continue;
q.push(v);
distances[v] = distances[u] + W[eid];
parent[v] = u;
}
}
return distances;
}
int solve_disconnected() {
vi parent(N, -1);
int reachable = 0;
ll cur_sum = 0;
priority_queue<pli> q;
q.push({0LL, X});
q.push({0LL, Y});
while (!q.empty()) {
ll dist = q.top().first, u = q.top().second;
q.pop();
if (dist + cur_sum > K) break;
reachable++;
cur_sum += dist;
for (int eid : adj[u]) {
int v = U[eid] == u ? V[eid] : U[eid];
if (v == parent[u]) continue;
q.push({W[eid], v});
}
}
return reachable;
}
int solve_line() {
}
int solve_small() {
}
int solve() {
}
/*
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) {
N = _N; X = _X; Y = _Y; 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(i);
adj[V[i]].push_back(i);
line = line && max(U[i], V[i]) == min(U[i], V[i]) + 1;
}
vi distX = compute_distances(X), distY = compute_distances(Y);
int ans = 0;
if (distX[Y] > 2 * K) {
ans = solve_disconnected();
} else if (line) {
ans = solve_line();
} else if (N <= 3000) {
ans = solve_small();
} else {
ans = solve();
}
return ans;
}
