Alpine valley

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int N,S,Q,E,shp[(int)2e5],I,D[(int)2e5];
vector<pair<int,pair<ll,int>>> v[(int)2e5];
vector<pair<int,int>> tiet;
int f[(int)2e5][32];

int ylös(int s,int k){
	for(;k;k^=(k&-k))
		s=f[s][__builtin_ctz(k)+1];
	return s;
}

int ylös_huono(int s,int k){
	for(;k;--k){
		s=f[s][1];
	}
	return s;
}

int aye(int a,int b){
	if(D[b]>D[a]) swap(a,b);
	a=ylös_huono(a,D[a]-D[b]);
	if(a==b) return a;
	for(int i=31;i;--i){
		if(f[a][i]!=f[b][i]){
			a=f[a][i];
			b=f[b][i];
		}
	}
	return f[a][1];
}

void haku(int s,int p,int d){
	f[s][0]=s;
	D[s]=d;
	for(auto u:v[s]){
		if(u.first==p) continue;
		f[u.first][1]=s;
		haku(u.first,s,d+1);
	}
}

int haye(int a,int b){
	if(D[b]>D[a]) swap(a,b);
	a=ylös_huono(a,D[a]-D[b]);
	while(a!=b){
		a=f[a][1];
		b=f[b][1];
	}
	return a;
}

bool reitillä(int a,int b,int s){
	if(s==a||s==b) return true;
	int ay=haye(a,b);
	if(D[s]<D[ay]) return false;
	if(D[a]>D[s]&&ylös_huono(a,D[a]-D[s])==s) return true;
	if(D[b]>D[s]&&ylös_huono(b,D[b]-D[s])==s) return true;
	return false;
}

set<int> res;

bool reitti(int a,int b,int p=-1){
	res.insert(a);
	if(a==b) return true;
	for(auto u:v[a]){
		if(u.first==p) continue;
		if(reitti(u.first,b,a)) return true;
	}
	res.erase(a);
	return false;
}

bool reitil2(int a,int b,int s){
	for(auto it=res.begin();it!=res.end();it=res.erase(it));
	reitti(a,b);
	if(res.count(s)) return true;
	return false;
}

bool ppako(int s){
	int a=tiet[I-1].first,b=tiet[I-1].second;
	return !(reitillä(s,E,a)&&reitillä(s,E,b));
}

bool pako(int s,int p){
	if(s==E) return true;
	for(auto u:v[s]){
		if(u.first==p||u.second.second==I) continue;
		if(pako(u.first,s)) return true;
	}
	return false;
}

ll etäisyys(int s){
	priority_queue<pair<ll,pair<int,int>>> q;
	q.push({0,{s,-1}});
	while(q.size()){
		auto p=q.top();q.pop();
		ll et=-p.first;
		int u=p.second.first;
		if(shp[u]) return et;

		for(auto B:v[u]){
			if(B.first==p.second.second||B.second.second==I) continue;
			q.push({-et-B.second.first,{B.first,u}});
		}
	}
	return -1;
}

void kysmys(){
	int R;
	cin>>I>>R;
	ll d;
	bool p=ppako(R);
	if(p){
		cout<<"escaped\n";
	} else if((d=etäisyys(R))==-1){
		cout<<"oo\n";
	} else {
		cout<<d<<'\n';
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>N>>S>>Q>>E;
	for(int i=0;i<N-1;++i){
		int A,B,W;
		cin>>A>>B>>W;
		v[A].push_back({B,{W,i+1}});
		v[B].push_back({A,{W,i+1}});
		tiet.push_back({A,B});
	}

	haku(1,-1,0);
	for(int i=1;i<=N;++i){
		for(int k=2;k<32&&f[i][k-1];++k){
			f[i][k]=f[f[i][k-1]][k-1];
		}
	}

	for(int i=1;i<N;++i){
		for(int j=1;j<D[i];j*=2){
			if(ylös(i,j)!=ylös_huono(i,j)){
				cerr<<"ei toimi: "<<i<<j<<'\n';;
				return 6;
			}
		}
	}

	for(int i=0;i<S;++i){
		int s; cin>>s;
		shp[s]=1;
	}

	for(int i=0;i<Q;++i){
		kysmys();
	}
}

Test 1

Group: 2, 4

Verdict: ACCEPTED

Test 2

Group: 2, 4

Verdict: ACCEPTED

Test 3

Group: 1, 4

Verdict: ACCEPTED

Test 4

Group: 1, 4

Verdict: ACCEPTED

Test 5

Group: 1, 4

Verdict: ACCEPTED

Test 6

Group: 1, 3, 4

Verdict: ACCEPTED

Test 7

Group: 2, 4

Verdict: RUNTIME ERROR

ei toimi: 34

Test 8

Group: 2, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 9

Group: 2, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 10

Group: 2, 4

Verdict: RUNTIME ERROR

ei toimi: 54

Test 11

Group: 2, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 12

Group: 2, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 13

Group: 2, 3, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 14

Group: 2, 3, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 15

Group: 2, 3, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 16

Group: 2, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 17

Group: 3, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 18

Group: 3, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 19

Group: 3, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 20

Group: 3, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 21

Group: 3, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 22

Group: 3, 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 23

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 24

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 25

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 26

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 27

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 28

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 29

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 30

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 31

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 32

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 33

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 34

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 35

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 36

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 37

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24

Test 38

Group: 4

Verdict: RUNTIME ERROR

ei toimi: 24