#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,pas,dep[50009],lf[50009],rg[50009],tim,msh[50009][19],pi;
vector <pair <int, int> > v[50009];
pair <int, int> p[9];
void dfsst(int q, int w){
tim++;
lf[q]=rg[q]=tim;
msh[q][0]=w;
for(int h=1; h<=17; h++){
msh[q][h]=msh[msh[q][h-1]][h-1];
}
for(vector <pair <int, int> >::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it).first==w) continue;
dep[(*it).first]=dep[q]+(*it).second;
dfsst((*it).first,q);
if(rg[q]<rg[(*it).first]) rg[q]=rg[(*it).first];
}
}
bool anc(int q, int w){
if(lf[q]<=lf[w]&&rg[q]>=rg[w]) return 1; else return 0;
}
int lca(int q, int w){
if(anc(q,w)) return q;
if(anc(w,q)) return w;
for(int h=17; h>=0; h--){
if(msh[q][h]==0||anc(msh[q][h],w)==1) continue;
q=msh[q][h];
}
return msh[q][0];
}
int dista(int q, int w){
return dep[q]+dep[w]-dep[lca(q,w)]*2;
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a;
for(i=1; i<a; i++){
cin>>c>>d>>e;c++;d++;
v[c].push_back({d,e});
v[d].push_back({c,e});
}
dfsst(1,0);
cin>>tes;
for(t=1; t<=tes; t++){
pi=5;
for(i=1; i<=pi; i++){
cin>>p[i].second;p[i].second++;
p[i].first=lf[p[i].second];
}
sort(p+1,p+pi+1);
p[pi+1]=p[1];pas=0;
for(i=1; i<=pi; i++){
pas+=dista(p[i].second,p[i+1].second);
}
pas/=2;
cout<<pas<<"\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
10176 KB |
Output is correct |
2 |
Correct |
39 ms |
11576 KB |
Output is correct |
3 |
Correct |
42 ms |
11600 KB |
Output is correct |
4 |
Correct |
49 ms |
11596 KB |
Output is correct |
5 |
Correct |
38 ms |
11488 KB |
Output is correct |
6 |
Correct |
43 ms |
11504 KB |
Output is correct |
7 |
Correct |
41 ms |
11576 KB |
Output is correct |
8 |
Correct |
46 ms |
11572 KB |
Output is correct |
9 |
Correct |
39 ms |
11500 KB |
Output is correct |
10 |
Correct |
43 ms |
11572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
8348 KB |
Output is correct |
2 |
Correct |
34 ms |
10700 KB |
Output is correct |
3 |
Correct |
34 ms |
10748 KB |
Output is correct |
4 |
Correct |
36 ms |
10708 KB |
Output is correct |
5 |
Correct |
38 ms |
10828 KB |
Output is correct |
6 |
Correct |
33 ms |
10748 KB |
Output is correct |
7 |
Correct |
36 ms |
10700 KB |
Output is correct |
8 |
Correct |
36 ms |
10692 KB |
Output is correct |
9 |
Correct |
35 ms |
10716 KB |
Output is correct |
10 |
Correct |
34 ms |
10640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1492 KB |
Output is correct |
2 |
Correct |
54 ms |
10176 KB |
Output is correct |
3 |
Correct |
39 ms |
11576 KB |
Output is correct |
4 |
Correct |
42 ms |
11600 KB |
Output is correct |
5 |
Correct |
49 ms |
11596 KB |
Output is correct |
6 |
Correct |
38 ms |
11488 KB |
Output is correct |
7 |
Correct |
43 ms |
11504 KB |
Output is correct |
8 |
Correct |
41 ms |
11576 KB |
Output is correct |
9 |
Correct |
46 ms |
11572 KB |
Output is correct |
10 |
Correct |
39 ms |
11500 KB |
Output is correct |
11 |
Correct |
43 ms |
11572 KB |
Output is correct |
12 |
Correct |
31 ms |
8348 KB |
Output is correct |
13 |
Correct |
34 ms |
10700 KB |
Output is correct |
14 |
Correct |
34 ms |
10748 KB |
Output is correct |
15 |
Correct |
36 ms |
10708 KB |
Output is correct |
16 |
Correct |
38 ms |
10828 KB |
Output is correct |
17 |
Correct |
33 ms |
10748 KB |
Output is correct |
18 |
Correct |
36 ms |
10700 KB |
Output is correct |
19 |
Correct |
36 ms |
10692 KB |
Output is correct |
20 |
Correct |
35 ms |
10716 KB |
Output is correct |
21 |
Correct |
34 ms |
10640 KB |
Output is correct |
22 |
Correct |
42 ms |
10092 KB |
Output is correct |
23 |
Correct |
35 ms |
8724 KB |
Output is correct |
24 |
Correct |
45 ms |
11036 KB |
Output is correct |
25 |
Correct |
47 ms |
11052 KB |
Output is correct |
26 |
Correct |
49 ms |
11116 KB |
Output is correct |
27 |
Correct |
47 ms |
11016 KB |
Output is correct |
28 |
Correct |
45 ms |
11096 KB |
Output is correct |
29 |
Correct |
45 ms |
11144 KB |
Output is correct |
30 |
Correct |
51 ms |
11120 KB |
Output is correct |
31 |
Correct |
56 ms |
11072 KB |
Output is correct |