#include <iostream>
#include <vector>
#include <set>
using namespace std;
int n,k,q,t_out[200003],p[200003][33];
vector<int>a[200003];
int ba[200003],t_in[200004],T,x;
set<int>s1[200003],s2[200003];
set<int>::iterator it1,it2;
bool is_it(int a,int b){
if (t_in[a]<=t_in[b]&&t_out[b]<=t_out[a]){
return true;
}else{
return false;
}
}
void go(int s,int parent){
t_in[s]=++T;
p[s][0]=parent;
int j=s;
for (int i=1;i<=30;i++){
p[j][i]=p[p[j][i-1]][i-1];
}
for(int i=0;i<(int)a[s].size();i++){
if(a[s][i]==parent)continue;
go(a[s][i],s);
}
t_out[s]=++T;
}
int lca(int a,int b){
if(t_in[a]>t_in[b]){
swap(a,b);
}
if(is_it(a,b)){
return a;
}
if(is_it(b,a)){
return b;
}
for(int i=30;i>=0;i--){
if(p[a][i]==0)continue;
if(is_it(p[a][i],b)==0){
a=p[a][i];
}
}
return p[a][0];
}
int u,v,tp;
int main() {ios_base::sync_with_stdio(false);
cin>>n>>k>>q;
for(int i=1;i<n;i++){
cin>>v>>u;
a[v].push_back(u);
a[u].push_back(v);
}
for(int i=1;i<=k;i++){
cin>>ba[i];
}
go(1,0);
for(int i=1;i<=k;i++){
s2[ba[i]].insert(i);
}
for(int i=1;i<k;i++){
s1[lca(ba[i],ba[i+1])].insert(i);
// cout<<lca(ba[i],ba[i+1])<<endl;
}
while(q--){
cin>>tp;
if(tp==1){
cin>>u>>v;
if(u>1){
s1[lca(ba[u-1],ba[u])].erase(u-1);
}
if(x<k){
s1[lca(ba[u],ba[u+1])].erase(u);
}
s2[ba[u]].erase(u);
ba[u]=v;
if(u>1){
s1[lca(ba[u-1],ba[u])].insert(u-1);
}
if(u<k){
s1[lca(ba[u],ba[u+1])].insert(u);
}
s2[ba[u]].insert(u);
}else{
cin>>u>>v>>x;
it1=s1[x].lower_bound(u);
it2=s2[x].lower_bound(u);
if(it2!=s2[x].end()&&(*it2)<=v){
cout<<(*it2)<<" "<<(*it2)<<endl;
}else{
if(it1!=s1[x].end()){
if((*it1)<v){
cout<<(*it1)<<" "<<(*it1)+1<<endl;
}
else{
cout<<-1<<" "<<-1<<endl;
}
}else
cout<<-1<<" "<<-1<<endl;
}
}
}
return 0;
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5
2 3
2 1
3 1
1 3 5
2 3 4 5
2 1 3 1
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
23800 KB |
n=5 |
2 |
Correct |
23 ms |
23928 KB |
n=100 |
3 |
Correct |
22 ms |
23800 KB |
n=100 |
4 |
Correct |
22 ms |
23928 KB |
n=100 |
5 |
Correct |
22 ms |
23804 KB |
n=100 |
6 |
Correct |
22 ms |
23800 KB |
n=100 |
7 |
Correct |
23 ms |
23848 KB |
n=100 |
8 |
Correct |
24 ms |
23804 KB |
n=100 |
9 |
Correct |
19 ms |
23800 KB |
n=100 |
10 |
Correct |
22 ms |
23800 KB |
n=100 |
11 |
Correct |
22 ms |
23800 KB |
n=100 |
12 |
Correct |
22 ms |
23800 KB |
n=100 |
13 |
Correct |
22 ms |
23800 KB |
n=100 |
14 |
Correct |
23 ms |
23928 KB |
n=100 |
15 |
Correct |
22 ms |
23828 KB |
n=100 |
16 |
Correct |
22 ms |
23812 KB |
n=100 |
17 |
Correct |
23 ms |
23800 KB |
n=100 |
18 |
Correct |
24 ms |
23908 KB |
n=100 |
19 |
Correct |
22 ms |
23800 KB |
n=100 |
20 |
Correct |
22 ms |
23800 KB |
n=100 |
21 |
Correct |
20 ms |
23800 KB |
n=100 |
22 |
Correct |
22 ms |
23800 KB |
n=100 |
23 |
Correct |
19 ms |
23800 KB |
n=100 |
24 |
Correct |
18 ms |
23928 KB |
n=100 |
25 |
Correct |
19 ms |
23848 KB |
n=100 |
26 |
Correct |
19 ms |
23800 KB |
n=12 |
27 |
Correct |
20 ms |
23800 KB |
n=100 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
23800 KB |
n=5 |
2 |
Correct |
23 ms |
23928 KB |
n=100 |
3 |
Correct |
22 ms |
23800 KB |
n=100 |
4 |
Correct |
22 ms |
23928 KB |
n=100 |
5 |
Correct |
22 ms |
23804 KB |
n=100 |
6 |
Correct |
22 ms |
23800 KB |
n=100 |
7 |
Correct |
23 ms |
23848 KB |
n=100 |
8 |
Correct |
24 ms |
23804 KB |
n=100 |
9 |
Correct |
19 ms |
23800 KB |
n=100 |
10 |
Correct |
22 ms |
23800 KB |
n=100 |
11 |
Correct |
22 ms |
23800 KB |
n=100 |
12 |
Correct |
22 ms |
23800 KB |
n=100 |
13 |
Correct |
22 ms |
23800 KB |
n=100 |
14 |
Correct |
23 ms |
23928 KB |
n=100 |
15 |
Correct |
22 ms |
23828 KB |
n=100 |
16 |
Correct |
22 ms |
23812 KB |
n=100 |
17 |
Correct |
23 ms |
23800 KB |
n=100 |
18 |
Correct |
24 ms |
23908 KB |
n=100 |
19 |
Correct |
22 ms |
23800 KB |
n=100 |
20 |
Correct |
22 ms |
23800 KB |
n=100 |
21 |
Correct |
20 ms |
23800 KB |
n=100 |
22 |
Correct |
22 ms |
23800 KB |
n=100 |
23 |
Correct |
19 ms |
23800 KB |
n=100 |
24 |
Correct |
18 ms |
23928 KB |
n=100 |
25 |
Correct |
19 ms |
23848 KB |
n=100 |
26 |
Correct |
19 ms |
23800 KB |
n=12 |
27 |
Correct |
20 ms |
23800 KB |
n=100 |
28 |
Correct |
24 ms |
24056 KB |
n=500 |
29 |
Correct |
20 ms |
24020 KB |
n=500 |
30 |
Correct |
20 ms |
23928 KB |
n=500 |
31 |
Correct |
20 ms |
23928 KB |
n=500 |
32 |
Correct |
19 ms |
23928 KB |
n=500 |
33 |
Correct |
20 ms |
23928 KB |
n=500 |
34 |
Correct |
20 ms |
23928 KB |
n=500 |
35 |
Correct |
21 ms |
23928 KB |
n=500 |
36 |
Correct |
21 ms |
23928 KB |
n=500 |
37 |
Correct |
20 ms |
23928 KB |
n=500 |
38 |
Correct |
19 ms |
24056 KB |
n=500 |
39 |
Correct |
20 ms |
23928 KB |
n=500 |
40 |
Correct |
23 ms |
24056 KB |
n=500 |
41 |
Correct |
20 ms |
23928 KB |
n=500 |
42 |
Correct |
20 ms |
24056 KB |
n=500 |
43 |
Correct |
20 ms |
23928 KB |
n=500 |
44 |
Correct |
21 ms |
23928 KB |
n=500 |
45 |
Correct |
25 ms |
24012 KB |
n=500 |
46 |
Correct |
21 ms |
23928 KB |
n=500 |
47 |
Correct |
19 ms |
23928 KB |
n=500 |
48 |
Correct |
19 ms |
23928 KB |
n=500 |
49 |
Correct |
19 ms |
23928 KB |
n=500 |
50 |
Correct |
20 ms |
23928 KB |
n=500 |
51 |
Correct |
20 ms |
23928 KB |
n=500 |
52 |
Correct |
19 ms |
24056 KB |
n=500 |
53 |
Correct |
21 ms |
23928 KB |
n=500 |
54 |
Correct |
20 ms |
23972 KB |
n=500 |
55 |
Correct |
19 ms |
23928 KB |
n=278 |
56 |
Correct |
19 ms |
23928 KB |
n=500 |
57 |
Correct |
20 ms |
23928 KB |
n=500 |
58 |
Correct |
19 ms |
23928 KB |
n=500 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
23800 KB |
n=5 |
2 |
Correct |
23 ms |
23928 KB |
n=100 |
3 |
Correct |
22 ms |
23800 KB |
n=100 |
4 |
Correct |
22 ms |
23928 KB |
n=100 |
5 |
Correct |
22 ms |
23804 KB |
n=100 |
6 |
Correct |
22 ms |
23800 KB |
n=100 |
7 |
Correct |
23 ms |
23848 KB |
n=100 |
8 |
Correct |
24 ms |
23804 KB |
n=100 |
9 |
Correct |
19 ms |
23800 KB |
n=100 |
10 |
Correct |
22 ms |
23800 KB |
n=100 |
11 |
Correct |
22 ms |
23800 KB |
n=100 |
12 |
Correct |
22 ms |
23800 KB |
n=100 |
13 |
Correct |
22 ms |
23800 KB |
n=100 |
14 |
Correct |
23 ms |
23928 KB |
n=100 |
15 |
Correct |
22 ms |
23828 KB |
n=100 |
16 |
Correct |
22 ms |
23812 KB |
n=100 |
17 |
Correct |
23 ms |
23800 KB |
n=100 |
18 |
Correct |
24 ms |
23908 KB |
n=100 |
19 |
Correct |
22 ms |
23800 KB |
n=100 |
20 |
Correct |
22 ms |
23800 KB |
n=100 |
21 |
Correct |
20 ms |
23800 KB |
n=100 |
22 |
Correct |
22 ms |
23800 KB |
n=100 |
23 |
Correct |
19 ms |
23800 KB |
n=100 |
24 |
Correct |
18 ms |
23928 KB |
n=100 |
25 |
Correct |
19 ms |
23848 KB |
n=100 |
26 |
Correct |
19 ms |
23800 KB |
n=12 |
27 |
Correct |
20 ms |
23800 KB |
n=100 |
28 |
Correct |
24 ms |
24056 KB |
n=500 |
29 |
Correct |
20 ms |
24020 KB |
n=500 |
30 |
Correct |
20 ms |
23928 KB |
n=500 |
31 |
Correct |
20 ms |
23928 KB |
n=500 |
32 |
Correct |
19 ms |
23928 KB |
n=500 |
33 |
Correct |
20 ms |
23928 KB |
n=500 |
34 |
Correct |
20 ms |
23928 KB |
n=500 |
35 |
Correct |
21 ms |
23928 KB |
n=500 |
36 |
Correct |
21 ms |
23928 KB |
n=500 |
37 |
Correct |
20 ms |
23928 KB |
n=500 |
38 |
Correct |
19 ms |
24056 KB |
n=500 |
39 |
Correct |
20 ms |
23928 KB |
n=500 |
40 |
Correct |
23 ms |
24056 KB |
n=500 |
41 |
Correct |
20 ms |
23928 KB |
n=500 |
42 |
Correct |
20 ms |
24056 KB |
n=500 |
43 |
Correct |
20 ms |
23928 KB |
n=500 |
44 |
Correct |
21 ms |
23928 KB |
n=500 |
45 |
Correct |
25 ms |
24012 KB |
n=500 |
46 |
Correct |
21 ms |
23928 KB |
n=500 |
47 |
Correct |
19 ms |
23928 KB |
n=500 |
48 |
Correct |
19 ms |
23928 KB |
n=500 |
49 |
Correct |
19 ms |
23928 KB |
n=500 |
50 |
Correct |
20 ms |
23928 KB |
n=500 |
51 |
Correct |
20 ms |
23928 KB |
n=500 |
52 |
Correct |
19 ms |
24056 KB |
n=500 |
53 |
Correct |
21 ms |
23928 KB |
n=500 |
54 |
Correct |
20 ms |
23972 KB |
n=500 |
55 |
Correct |
19 ms |
23928 KB |
n=278 |
56 |
Correct |
19 ms |
23928 KB |
n=500 |
57 |
Correct |
20 ms |
23928 KB |
n=500 |
58 |
Correct |
19 ms |
23928 KB |
n=500 |
59 |
Correct |
25 ms |
24440 KB |
n=2000 |
60 |
Correct |
23 ms |
24412 KB |
n=2000 |
61 |
Correct |
24 ms |
24428 KB |
n=2000 |
62 |
Correct |
24 ms |
24440 KB |
n=2000 |
63 |
Correct |
23 ms |
24440 KB |
n=2000 |
64 |
Correct |
23 ms |
24440 KB |
n=2000 |
65 |
Correct |
29 ms |
24312 KB |
n=2000 |
66 |
Correct |
23 ms |
24440 KB |
n=2000 |
67 |
Correct |
24 ms |
24312 KB |
n=2000 |
68 |
Correct |
24 ms |
24440 KB |
n=2000 |
69 |
Correct |
25 ms |
24440 KB |
n=2000 |
70 |
Correct |
27 ms |
24352 KB |
n=2000 |
71 |
Correct |
29 ms |
24312 KB |
n=2000 |
72 |
Correct |
24 ms |
24440 KB |
n=2000 |
73 |
Correct |
27 ms |
24312 KB |
n=2000 |
74 |
Correct |
26 ms |
24440 KB |
n=1844 |
75 |
Correct |
28 ms |
24344 KB |
n=2000 |
76 |
Correct |
29 ms |
24440 KB |
n=2000 |
77 |
Correct |
27 ms |
24312 KB |
n=2000 |
78 |
Correct |
27 ms |
24312 KB |
n=2000 |
79 |
Correct |
27 ms |
24312 KB |
n=2000 |
80 |
Correct |
23 ms |
24440 KB |
n=2000 |
81 |
Correct |
29 ms |
24440 KB |
n=2000 |
82 |
Correct |
28 ms |
24412 KB |
n=2000 |
83 |
Correct |
28 ms |
24440 KB |
n=2000 |
84 |
Correct |
28 ms |
24356 KB |
n=2000 |
85 |
Correct |
28 ms |
24440 KB |
n=2000 |
86 |
Correct |
28 ms |
24396 KB |
n=2000 |
87 |
Correct |
24 ms |
24312 KB |
n=2000 |
88 |
Correct |
23 ms |
24440 KB |
n=2000 |
89 |
Correct |
26 ms |
24440 KB |
n=2000 |
90 |
Correct |
27 ms |
24436 KB |
n=2000 |
91 |
Correct |
29 ms |
24440 KB |
n=2000 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
23800 KB |
n=5 |
2 |
Correct |
23 ms |
23928 KB |
n=100 |
3 |
Correct |
22 ms |
23800 KB |
n=100 |
4 |
Correct |
22 ms |
23928 KB |
n=100 |
5 |
Correct |
22 ms |
23804 KB |
n=100 |
6 |
Correct |
22 ms |
23800 KB |
n=100 |
7 |
Correct |
23 ms |
23848 KB |
n=100 |
8 |
Correct |
24 ms |
23804 KB |
n=100 |
9 |
Correct |
19 ms |
23800 KB |
n=100 |
10 |
Correct |
22 ms |
23800 KB |
n=100 |
11 |
Correct |
22 ms |
23800 KB |
n=100 |
12 |
Correct |
22 ms |
23800 KB |
n=100 |
13 |
Correct |
22 ms |
23800 KB |
n=100 |
14 |
Correct |
23 ms |
23928 KB |
n=100 |
15 |
Correct |
22 ms |
23828 KB |
n=100 |
16 |
Correct |
22 ms |
23812 KB |
n=100 |
17 |
Correct |
23 ms |
23800 KB |
n=100 |
18 |
Correct |
24 ms |
23908 KB |
n=100 |
19 |
Correct |
22 ms |
23800 KB |
n=100 |
20 |
Correct |
22 ms |
23800 KB |
n=100 |
21 |
Correct |
20 ms |
23800 KB |
n=100 |
22 |
Correct |
22 ms |
23800 KB |
n=100 |
23 |
Correct |
19 ms |
23800 KB |
n=100 |
24 |
Correct |
18 ms |
23928 KB |
n=100 |
25 |
Correct |
19 ms |
23848 KB |
n=100 |
26 |
Correct |
19 ms |
23800 KB |
n=12 |
27 |
Correct |
20 ms |
23800 KB |
n=100 |
28 |
Correct |
24 ms |
24056 KB |
n=500 |
29 |
Correct |
20 ms |
24020 KB |
n=500 |
30 |
Correct |
20 ms |
23928 KB |
n=500 |
31 |
Correct |
20 ms |
23928 KB |
n=500 |
32 |
Correct |
19 ms |
23928 KB |
n=500 |
33 |
Correct |
20 ms |
23928 KB |
n=500 |
34 |
Correct |
20 ms |
23928 KB |
n=500 |
35 |
Correct |
21 ms |
23928 KB |
n=500 |
36 |
Correct |
21 ms |
23928 KB |
n=500 |
37 |
Correct |
20 ms |
23928 KB |
n=500 |
38 |
Correct |
19 ms |
24056 KB |
n=500 |
39 |
Correct |
20 ms |
23928 KB |
n=500 |
40 |
Correct |
23 ms |
24056 KB |
n=500 |
41 |
Correct |
20 ms |
23928 KB |
n=500 |
42 |
Correct |
20 ms |
24056 KB |
n=500 |
43 |
Correct |
20 ms |
23928 KB |
n=500 |
44 |
Correct |
21 ms |
23928 KB |
n=500 |
45 |
Correct |
25 ms |
24012 KB |
n=500 |
46 |
Correct |
21 ms |
23928 KB |
n=500 |
47 |
Correct |
19 ms |
23928 KB |
n=500 |
48 |
Correct |
19 ms |
23928 KB |
n=500 |
49 |
Correct |
19 ms |
23928 KB |
n=500 |
50 |
Correct |
20 ms |
23928 KB |
n=500 |
51 |
Correct |
20 ms |
23928 KB |
n=500 |
52 |
Correct |
19 ms |
24056 KB |
n=500 |
53 |
Correct |
21 ms |
23928 KB |
n=500 |
54 |
Correct |
20 ms |
23972 KB |
n=500 |
55 |
Correct |
19 ms |
23928 KB |
n=278 |
56 |
Correct |
19 ms |
23928 KB |
n=500 |
57 |
Correct |
20 ms |
23928 KB |
n=500 |
58 |
Correct |
19 ms |
23928 KB |
n=500 |
59 |
Correct |
25 ms |
24440 KB |
n=2000 |
60 |
Correct |
23 ms |
24412 KB |
n=2000 |
61 |
Correct |
24 ms |
24428 KB |
n=2000 |
62 |
Correct |
24 ms |
24440 KB |
n=2000 |
63 |
Correct |
23 ms |
24440 KB |
n=2000 |
64 |
Correct |
23 ms |
24440 KB |
n=2000 |
65 |
Correct |
29 ms |
24312 KB |
n=2000 |
66 |
Correct |
23 ms |
24440 KB |
n=2000 |
67 |
Correct |
24 ms |
24312 KB |
n=2000 |
68 |
Correct |
24 ms |
24440 KB |
n=2000 |
69 |
Correct |
25 ms |
24440 KB |
n=2000 |
70 |
Correct |
27 ms |
24352 KB |
n=2000 |
71 |
Correct |
29 ms |
24312 KB |
n=2000 |
72 |
Correct |
24 ms |
24440 KB |
n=2000 |
73 |
Correct |
27 ms |
24312 KB |
n=2000 |
74 |
Correct |
26 ms |
24440 KB |
n=1844 |
75 |
Correct |
28 ms |
24344 KB |
n=2000 |
76 |
Correct |
29 ms |
24440 KB |
n=2000 |
77 |
Correct |
27 ms |
24312 KB |
n=2000 |
78 |
Correct |
27 ms |
24312 KB |
n=2000 |
79 |
Correct |
27 ms |
24312 KB |
n=2000 |
80 |
Correct |
23 ms |
24440 KB |
n=2000 |
81 |
Correct |
29 ms |
24440 KB |
n=2000 |
82 |
Correct |
28 ms |
24412 KB |
n=2000 |
83 |
Correct |
28 ms |
24440 KB |
n=2000 |
84 |
Correct |
28 ms |
24356 KB |
n=2000 |
85 |
Correct |
28 ms |
24440 KB |
n=2000 |
86 |
Correct |
28 ms |
24396 KB |
n=2000 |
87 |
Correct |
24 ms |
24312 KB |
n=2000 |
88 |
Correct |
23 ms |
24440 KB |
n=2000 |
89 |
Correct |
26 ms |
24440 KB |
n=2000 |
90 |
Correct |
27 ms |
24436 KB |
n=2000 |
91 |
Correct |
29 ms |
24440 KB |
n=2000 |
92 |
Correct |
1194 ms |
82172 KB |
n=200000 |
93 |
Correct |
1118 ms |
90624 KB |
n=200000 |
94 |
Correct |
1108 ms |
93760 KB |
n=200000 |
95 |
Correct |
935 ms |
85340 KB |
n=200000 |
96 |
Correct |
963 ms |
85448 KB |
n=200000 |
97 |
Correct |
1154 ms |
89520 KB |
n=200000 |
98 |
Correct |
1024 ms |
85272 KB |
n=200000 |
99 |
Correct |
1091 ms |
85604 KB |
n=200000 |
100 |
Correct |
1025 ms |
85488 KB |
n=200000 |
101 |
Correct |
1010 ms |
95128 KB |
n=200000 |
102 |
Correct |
767 ms |
86648 KB |
n=200000 |
103 |
Correct |
783 ms |
86792 KB |
n=200000 |
104 |
Correct |
703 ms |
86628 KB |
n=200000 |
105 |
Correct |
717 ms |
86904 KB |
n=200000 |
106 |
Correct |
700 ms |
87156 KB |
n=200000 |
107 |
Correct |
722 ms |
87240 KB |
n=200000 |
108 |
Correct |
956 ms |
85496 KB |
n=200000 |
109 |
Correct |
956 ms |
85488 KB |
n=200000 |
110 |
Correct |
946 ms |
85552 KB |
n=200000 |
111 |
Correct |
1132 ms |
84976 KB |
n=200000 |
112 |
Correct |
1039 ms |
94200 KB |
n=200000 |
113 |
Correct |
1491 ms |
89592 KB |
n=200000 |
114 |
Correct |
1185 ms |
85120 KB |
n=200000 |
115 |
Correct |
1619 ms |
87488 KB |
n=200000 |
116 |
Correct |
1149 ms |
85580 KB |
n=200000 |
117 |
Correct |
889 ms |
94456 KB |
n=200000 |
118 |
Correct |
1351 ms |
88572 KB |
n=200000 |
119 |
Correct |
1075 ms |
85648 KB |
n=200000 |
120 |
Correct |
929 ms |
94144 KB |
n=200000 |
121 |
Correct |
771 ms |
93944 KB |
n=200000 |
122 |
Correct |
807 ms |
94464 KB |
n=200000 |
123 |
Correct |
816 ms |
87032 KB |
n=200000 |
124 |
Correct |
288 ms |
40060 KB |
n=25264 |