#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = 100005;
int up[MAXN][20];
int path[MAXN];
ll depth[MAXN];
int ed[MAXN];
bool shop[MAXN];
ll sh[MAXN];
ll dp[MAXN][20];
vector<vector<pair<int,pair<ll,int>>>> v;
void dfs(int x, int prev){
up[x][0] = prev;
for (auto nxt : v[x]){
if (nxt.first == prev) continue;
path[nxt.first] = path[x] + 1;
depth[nxt.first] = depth[x] + nxt.second.first;
ed[nxt.second.second] = nxt.first;
dfs(nxt.first, x);
sh[x] = min(sh[x], sh[nxt.first]+nxt.second.first);
}
dp[x][0] = sh[x] == 1e18 ? 1e18 : sh[x] - depth[x];
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n, s, q, e; cin >> n >> s >> q >> e;
v.resize(n);
fill(ed, ed+n, -1);
for (int i = 1; i < n; i++){
int a, b; ll w;
cin >> a >> b >> w;
a--, b--;
v[a].push_back({b, {w, i}});
v[b].push_back({a, {w, i}});
}
fill(shop, shop+n, 0);
fill(sh, sh+n, 1e18);
for (int i = 0; i < s; i++){
int sho; cin >> sho;
sho--;
shop[sho] = 1;
sh[sho] = 0;
}
e--;
path[e] = 0;
depth[e] = 0;
dfs(e, -1);
ll mini = 1e18;
for (int i = 1; i < 20; i++){
for (int j = 0; j < n; j++){
up[j][i] = up[j][i-1] == -1 ? -1 : up[up[j][i-1]][i-1];
dp[j][i] = up[j][i-1] == -1 ? dp[j][i-1] : min(dp[j][i-1], dp[up[j][i-1]][i-1]);
}
}
for (int i = 0; i < q; i++){
int a, b; cin >> a >> b;
b--;
a = ed[a];
ll prev = depth[b];
ll res = min(dp[a][0]+prev, sh[b]);
if (path[a] > path[b]){
cout << "escaped\n";
continue;
}
for (int j = 0; j < 20; j++){
if ((1<<j)&(path[b]-path[a])){
res = min(res, dp[b][j] + prev);
b = up[b][j];
}
}
if (b != a){
cout << "escaped\n";
}else if (res == mini){
cout << "oo\n";
}else{
cout << (res) << "\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... |