////!pragma //const int N = 1e5+5; //vl adj[N],cost[N]; //ll depth[N],root_dist[N],shop_dist[N],dir_par[N]; //bool is_shop[N]; //void dfs(int u, int p = -1){ // shop_dist[u] = is_shop[u] ? 0 : INF; // for(int i = 0; i < sz(adj[u]); ++i){ // int v = adj[u][i]; // if(v == p) continue; // dir_par[v] = u; // depth[v] = depth[u]+1; // root_dist[v] = root_dist[u]+cost[u][i]; // dfs(v,u); // shop_dist[u] = min(shop_dist[u],shop_dist[v]+cost[u][i]); // } //} //int n,e; //const int W = 150; //ll cheat_up[N], cheat_w[N]; //vl rdfs_order; //void opti(int u, int p = -1){ // while(cheat_up[u] != e && shop_dist[cheat_up[u]] >= shop_dist[u]) // cheat_up[u] = cheat_up[cheat_up[u]]; // for(int i = 0; i < sz(adj[u]); ++i){ // int v = adj[u][i]; // if(v == p) continue; // cheat_up[v] = u; // opti(v,u); // } //} //void prep_cheat(){ // cheat_up[e] = e; // opti(e); // for(int i = 1; i <= n; ++i){ // cheat_w[i] = cheat_up[i]; // for(int j = 0; j < W; ++j) // cheat_w[j] = cheat_up[cheat_w[j]]; // } //} //vpii edges; //int get_block(int id){ // int u,v; // tie(u,v) = edges[id-1]; // return depth[u] > depth[v] ? u : v; //} //const int K = 17; //int par[K][N]; //void lca_prep(){ // for(int u = 1; u <= n; ++u) // par[0][u] = dir_par[u]; // for(int s = 1; s < K; ++s) // for(int u = 1; u <= n; ++u) // par[s][u] = par[s-1][par[s-1][u]]; //} //int get_lca(int u, int v){ // if(depth[u] < depth[v]) // swap(u,v); // for(int k = K-1; k >= 0; --k) // if(depth[par[k][u]] >= depth[v]) // u = par[k][u]; // if(u == v) // return u; // for(int k = K-1; k >= 0; --k) // if(par[k][u] != par[k][v]){ // u = par[k][u]; // v = par[k][v]; // } // return par[0][u]; //} //string solve(int u, int block){ // //first part: correct: can we escape? // int lca = get_lca(u,block); // if(lca != block) // return "escaped"; // //watch(u); // //watch(block); // //watch(lca); // //second part: cheating, TODO: find a test to break this // ll ans = INF; // for(int v = u; ;){ // if(depth[v] < depth[block]) // break; // if(shop_dist[v] != INF) // ans = min(ans,shop_dist[v]); // if(depth[cheat_w[v]] >= depth[block]){ // v = cheat_w[v]; // } // else // v = cheat_up[v]; // } // if(ans == INF) return "oo"; // return to_string(ans+root_dist[u]); //} //void _(){ // int s,q; // cin >> n >> s >> q >> e; // for(int i = 0; i < n-1; ++i){ // int a,b,w; // cin >> a >> b >> w; // adj[a].pb(b); // adj[b].pb(a); // cost[a].pb(w); // cost[b].pb(w); // edges.pb({a,b}); // } // for(int i = 0; i < s; ++i){ // int u; // cin >> u; // is_shop[u] = true; // } // depth[e] = 1; // dfs(e); // for(int i = 1; i <= n; ++i) // if(shop_dist[i] != INF) // shop_dist[i] -= root_dist[i]; // prep_cheat(); // lca_prep(); // //watch(root_dist[3]); // //watch(shop_dist[3]); // //watch(root_dist[5]); // for(int i = 0; i < q; ++i){ // int id,u; // cin >> id >> u; // int block = get_block(id); // print(solve(u,block)); // } //} #pragma GCC optimize("Ofast") #include <stack> #include <iomanip> #include <algorithm> #include <cassert> #include <vector> #include <utility> #include <iostream> #include <string> #define pb push_back #define all(v) (v).begin(), (v).end() #define sz(v) ll(v.size()) #define T1 template<typename T> static using namespace std; typedef long long ll; typedef vector<ll> vl; typedef pair<int, int> pii; typedef vector<pii> vpii; const ll INF = ll(2e18) + 666; T1 ostream& operator<<(ostream& stream, const vector<T>& t); T1 void print(T x, string end = "\n"){ cout << x << end; } //!pragma const int N = 1e5+5; vl adj[N],cost[N]; ll depth[N],root_dist[N],shop_dist[N],dir_par[N]; bool is_shop[N]; void dfs(int u, int p = -1){ shop_dist[u] = is_shop[u] ? 0 : INF; for(int i = 0; i < sz(adj[u]); ++i){ int v = adj[u][i]; if(v == p) continue; dir_par[v] = u; depth[v] = depth[u]+1; root_dist[v] = root_dist[u]+cost[u][i]; dfs(v,u); shop_dist[u] = min(shop_dist[u],shop_dist[v]+cost[u][i]); } } int n,e; const int W = 250; ll cheat_up[N], cheat_w[N]; int up_by_w[N]; void opti(int u, int p = -1){ while(cheat_up[u] != e && shop_dist[cheat_up[u]] >= shop_dist[u]){ int w = up_by_w[cheat_up[u]]; if(w != e && shop_dist[w] >= shop_dist[u]) cheat_up[u] = w; else cheat_up[u] = cheat_up[cheat_up[u]]; } up_by_w[u] = cheat_up[u]; for(int i = 0; i < W; ++i) up_by_w[u] = cheat_up[up_by_w[u]]; for(int i = 0; i < sz(adj[u]); ++i){ int v = adj[u][i]; if(v == p) continue; cheat_up[v] = u; opti(v,u); } } void prep_cheat(){ cheat_up[e] = e; opti(e); for(int i = 1; i <= n; ++i){ cheat_w[i] = cheat_up[i]; for(int j = 0; j < W; ++j) cheat_w[i] = cheat_up[cheat_w[i]]; } } vpii edges; int get_block(int id){ int u,v; tie(u,v) = edges[id-1]; return depth[u] > depth[v] ? u : v; } const int K = 17; int par[K][N]; void lca_prep(){ for(int u = 1; u <= n; ++u) par[0][u] = dir_par[u]; for(int s = 1; s < K; ++s) for(int u = 1; u <= n; ++u) par[s][u] = par[s-1][par[s-1][u]]; } int get_lca(int u, int v){ if(depth[u] < depth[v]) swap(u,v); for(int k = K-1; k >= 0; --k) if(depth[par[k][u]] >= depth[v]) u = par[k][u]; if(u == v) return u; for(int k = K-1; k >= 0; --k) if(par[k][u] != par[k][v]){ u = par[k][u]; v = par[k][v]; } return par[0][u]; } string solve(int u, int block){ int lca = get_lca(u,block); if(lca != block) return "escaped"; ll ans = INF; for(int v = u; ;){ if(depth[v] < depth[block]) break; while(depth[cheat_w[v]] >= depth[block]){ //cerr << "called: " << depth[v] << ' ' << depth[cheat_w[v]] << '\n'; v = cheat_w[v]; } if(shop_dist[v] != INF) ans = min(ans,shop_dist[v]); v = cheat_up[v]; } if(ans == INF) return "oo"; return to_string(ans+root_dist[u]); } void _(){ int s,q; cin >> n >> s >> q >> e; for(int i = 0; i < n-1; ++i){ int a,b,w; cin >> a >> b >> w; adj[a].pb(b); adj[b].pb(a); cost[a].pb(w); cost[b].pb(w); edges.pb({a,b}); } for(int i = 0; i < s; ++i){ int u; cin >> u; is_shop[u] = true; } depth[e] = 1; dfs(e); for(int i = 1; i <= n; ++i) if(shop_dist[i] != INF) shop_dist[i] -= root_dist[i]; prep_cheat(); lca_prep(); //cerr << "prep done\n"; //watch(root_dist[3]); //watch(shop_dist[3]); //watch(root_dist[5]); for(int i = 0; i < q; ++i){ int id,u; cin >> id >> u; int block = get_block(id); print(solve(u,block)); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); _(); }