#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
ll timer = 0;
ll in[100001],out[100001];
vector<pair<ll,ll>> adj[100001];
set<ll> shops;
void dfs(ll u, ll p){
in[u] = timer++;
for(auto [v,w] : adj[u]){
if(v != p) dfs(v,u);
}
out[u] = timer++;
}
bool is_ancestor(ll up, ll low){
return (in[up] <= in[low] && out[up] >= out[low]);
}
ll bfs(ll u){
ll res = LLONG_MAX;
bool vis[100001];
queue<pair<ll,ll>> q;
vis[u] = true;
q.push({u,0});
while(!q.empty()){
pair<ll,ll> parent = q.front(); q.pop();
if(shops.count(parent.first)) res = min(res, parent.second);
for(auto child : adj[parent.first]){
if(!vis[child.first]){
vis[child.first] = true;
q.push({child.first, parent.second + child.second});
}
}
}
return res;
}
void solve()
{
ll n,s,q,e,a,b;
cin >> n >> s >> q >> e;
vector<vector<ll>> lista(n, vector<ll>(3, 0));
for(int i = 0; i < n-1; i++){
for(int j = 0; j < 3; j++) cin >> lista[i][j];
}
for(auto el : lista){
adj[el[0]].pb({el[1], el[2]});
adj[el[1]].pb({el[0], el[2]});
}
for(ll i = 0; i < s; i++){
cin >> a;
shops.emplace(a);
}
dfs(e, e);
// for(ll i = 0; i < n+1; i++) dbg(i, in[i], out[i]);
for(int i = 0; i < q; i++){
cin >> a >> b;
// dbg(lista[a-1][0], lista[a-1][1]);
if(is_ancestor(lista[a-1][0],b) && is_ancestor(lista[a-1][1],b)){
adj[lista[a-1][0]].erase(find(adj[lista[a-1][0]].begin(), adj[lista[a-1][0]].end(), make_pair(lista[a-1][1], lista[a-1][2])));
adj[lista[a-1][1]].erase(find(adj[lista[a-1][1]].begin(), adj[lista[a-1][1]].end(), make_pair(lista[a-1][0], lista[a-1][2])));
ll res = bfs(b);
// dbg(res);
cout << (res == LLONG_MAX ? "oo" : to_string(res)) << endl;
adj[lista[a-1][0]].pb({lista[a-1][1], lista[a-1][2]});
adj[lista[a-1][1]].pb({lista[a-1][0], lista[a-1][2]});
}
else{
cout << "escaped\n";
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
# | 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... |