#include <bits/stdc++.h>
using namespace std;
struct road {
int v1, v2;
};
using ll = long long;
vector<road> roads;
vector<vector<pair<int, int>>> adj(100005);
ll dist[100005], magic[100005];
int tin[100005], tout[100005];
int jumpMagic[100005][26];
ll minMagic[100005][26];
set<int> shop_nodes;
const ll INF = 2e16+5;
const int MAXK = 25;
int timer = 0;
void dfs(int u, int p, ll d) {
dist[u] = d;
tin[u] = ++timer;
for(auto[v, w] : adj[u]) {
if(v == p) continue;
dfs(v, u, d + w);
}
tout[u] = ++timer;
}
void calc_magic(int u, int p) {
magic[u] = INF;
for (auto [v, w] : adj[u]) {
if (v == p) continue;
calc_magic(v, u);
magic[u] = min(magic[u], magic[v]);
}
if (shop_nodes.count(u))
magic[u] = min(magic[u], dist[u]);
}
void lift(int u, int p) {
minMagic[u][0] = magic[u];
jumpMagic[u][0] = p;
for(int k = 1; k <= MAXK; ++k) {
jumpMagic[u][k] = jumpMagic[jumpMagic[u][k - 1]][k - 1];
minMagic[u][k] = min(minMagic[u][k - 1], minMagic[jumpMagic[u][k - 1]][k - 1]);
}
for(auto [v, w] : adj[u]) {
if(v == p) continue;
lift(v, u);
}
}
bool is_anc(int u, int v) {
return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, S, Q, E; cin >> N >> S >> Q >> E; // rooted at E
for(int i = 0, u, v, w; i < N - 1; ++i) {
cin >> u >> v >> w;
roads.push_back({u, v});
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(E, 0, 0LL);
for(int i = 0, c; i < S; ++i) {
cin >> c;
shop_nodes.insert(c);
}
magic[0] = INF;
calc_magic(E, 0);
for(int i = 1; i <= N; ++i)
if(magic[i] < INF) magic[i] -= 2 * dist[i];
lift(E, 0);
int I, R;
for(int i = 0; i < Q; ++i) {
cin >> I >> R;
int START = R;
--I;
int v1 = roads[I].v1, v2 = roads[I].v2;
if(dist[v1] < dist[v2]) swap(v1, v2);
if(!is_anc(R, v1)) {
cout << "escaped\n";
continue;
}
ll best = magic[R];
for(int k = MAXK; k >= 0; --k) {
if(is_anc(jumpMagic[R][k], v1) && jumpMagic[R][k] != v1) {
best = min(best, minMagic[R][k]);
R = jumpMagic[R][k];
}
}
best = min(best, magic[v1]);
if(best == INF) cout << "oo\n";
else cout << best + dist[START] << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |