#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#ifdef IOI
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__);
#else
#define dbg(...) 1337;
#endif
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=2e5+100;
const int LOGN=20;
int up[MAXN][LOGN+1];
vector<pair<int,int>> v[MAXN];
vector<vector<int>> ed;
int depth1[MAXN];
int depth2[MAXN];
int tin[MAXN];
int tout[MAXN];
int t=1;
void dfs(int node,int par=0){
tin[node]=t++;
depth1[node]=depth1[par]+1;
up[node][0]=par;
for(int i=1;i<=LOGN;i++)
up[node][i]=up[up[node][i-1]][i-1];
for(auto x:v[node]){
if(x.F==par) continue;
depth2[x.F]=depth2[node]+x.S;
dfs(x.F,node);
}
tout[node]=t++;
}
bool is_ancestor(int u, int v)
{
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int LCA(int a,int b){
if(depth1[a]<depth1[b]) swap(a,b);
int d=depth1[a]-depth1[b];
for(int i=LOGN;i>=0;i--){
if((1LL<<i)&d){
a=up[a][i];
}
}
if(a==b) return a;
for(int i=LOGN;i>=0;i--){
if(up[a][i]!=up[b][i]){
a=up[a][i];
b=up[b][i];
}
}
return up[a][0];
}
vector<int> sh;
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,s,q,e;
cin>>n>>s>>q>>e;
for(int i=1;i<n;i++){
int a,b;
int c;
cin>>a>>b>>c;
ed.pb({a,b});
v[a].pb(make_pair(b,c));
v[b].pb(make_pair(a,c));
}
dfs(e);
for(int i=0;i<s;i++){
int sx;
cin>>sx;
sh.pb(sx);
}
for(int i=0;i<q;i++){
int p,r;
cin>>p>>r;
p--;
int a=ed[p][0],b=ed[p][1];
// dbg(a,b,LCA(r,a),LCA(r,b))
if(!(is_ancestor(a,r)&&is_ancestor(b,r))){
cout<<"escaped"<<endl;
continue;
}
// int ans=1e18;
// for(auto y:sh){
// int x=y;
// // dbg(x)
// int l=LCA(r,x);
// if(is_ancestor(a,r)&&is_ancestor(b,r)&&is_ancestor(l,a)&&is_ancestor(l,b)){
// continue;
// }
// if(is_ancestor(a,x)&&is_ancestor(b,x)&&is_ancestor(l,a)&&is_ancestor(l,b)){
// continue;
// }
// ans=min(ans,depth2[x]+depth2[r]-2*depth2[l]);
// }
// if(ans==1e18){
// cout<<"oo"<<endl;
// continue;
// }
cout<<0<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
41208 KB |
Output is correct |
| 2 |
Correct |
126 ms |
45308 KB |
Output is correct |
| 3 |
Correct |
115 ms |
45612 KB |
Output is correct |
| 4 |
Correct |
139 ms |
47584 KB |
Output is correct |
| 5 |
Correct |
117 ms |
46068 KB |
Output is correct |
| 6 |
Correct |
162 ms |
48284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
