#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;
}
struct BFSNode {
int u, s; ll dist;
BFSNode(int u, int s, ll dist) {
this->u = u;
this->s = s;
this->dist = dist;
}
bool operator<(const BFSNode &other) const {
return dist < other.dist;
}
bool operator>(const BFSNode &other) const {
return dist > other.dist;
}
};
int solve_disconnected() {
vector<vector<bool>> vis(2, vector<bool>(N, false));
vl tim(N+1, 0LL);
int reachable = 0;
ll cur_sum = 0;
priority_queue<BFSNode, vector<BFSNode>, greater<BFSNode>> q;
q.push(BFSNode(X, 0, 0LL));
q.push(BFSNode(Y, 1, 0LL));
while (!q.empty()) {
BFSNode cur = q.top();
int u = cur.u, s = cur.s;
ll dist = cur.dist;
q.pop();
if (vis[s][u]) continue;
vis[s][u] = true;
// cout << "Node = " << u << " Source = " << s << " Dist = " << dist << "\n";
// cout << "Current Sum = " << cur_sum << "\n";
if (dist + cur_sum > K) continue;
reachable++;
cur_sum += dist;
tim[u] += dist;
for (int eid : adj[u]) {
int v = U[eid] == u ? V[eid] : U[eid];
if (vis[s][v]) continue;
ll ndist = tim[u] + W[eid] - tim[v];
// cout << "Neighbour = " << v << " Cost = " << ndist << "\n";
q.push(BFSNode(v, cur.s, max(0LL, ndist)));
}
}
return reachable;
}
int solve_line() {
int reachable = 0;
return reachable;
}
int solve_small() {
int reachable = 0;
return reachable;
}
int solve() {
int reachable = 0;
return reachable;
}
/*
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);
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());
// cout << "N = " << N << " X = " << X << " Y = " << Y << " K = " << K << "\n";
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 solve_disconnected();
}
