#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);
vector<int>g[N];
int a[N];
int timer,tin[N],tout[N];
int up[20][N];
void dfs(int v,int p){
up[0][v]=p;
tin[v]=++timer;
for(int i=1;i<=19;i++){
up[i][v]=up[i-1][up[i-1][v]];
}
for(auto to:g[v])
if(to!=p)dfs(to,v);
tout[v]=++timer;
}
bool upper(int a,int b){
return tin[a]<=tin[b]&&tout[a]>=tout[b];
}
int lca(int a,int b){
if(upper(a,b))return a;
if(upper(b,a))return b;
for(int i=19;i>=0;--i){
if(!upper(up[i][a],b)){
a=up[i][a];
//cerr<<a<<' ';
}
}
return up[0][a];
}
set<pair<int,int>>s[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
g[a].pb(b);
g[b].pb(a);
}
dfs(1,1);
for(int i=1;i<=m;i++){
cin>>a[i];
s[a[i]].insert({i,i});
if(i>1)s[lca(a[i-1],a[i])].insert({i-1,i});
}
/*for(int i=1;i<=n;i++){
cout<<i<<" ";
for(auto x:s[i])
cout<<x.first<<' '<<x.second<<" | ";
cout<<'\n';
} */
for(int i=0;i<q;i++){
int com;
cin>>com;
if(com==1){
int p,v;
cin>>p>>v;
s[a[p]].erase({p,p});
if(p>1)s[lca(a[p-1],a[p])].erase({p-1,p});
if(p<m)s[lca(a[p],a[p+1])].erase({p,p+1});
a[p]=v;
s[a[p]].insert({p,p});
if(p>1)s[lca(a[p-1],a[p])].insert({p-1,p});
if(p<m)s[lca(a[p],a[p+1])].insert({p,p+1});
}else{
int l,r,v;
cin>>l>>r>>v;
int le=-1,ri=-1;
auto it=s[v].lower_bound({l,0});
if(it!=s[v].end()){
if(it->second<=r){
le=it->first;
ri=it->second;
}
//cerr<<it->first<<' '<<it->second<<'\n';
}
cout<<le<<' '<<ri<<'\n';
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
14712 KB |
n=5 |
2 |
Correct |
15 ms |
14584 KB |
n=100 |
3 |
Correct |
15 ms |
14584 KB |
n=100 |
4 |
Correct |
18 ms |
14584 KB |
n=100 |
5 |
Correct |
15 ms |
14584 KB |
n=100 |
6 |
Correct |
17 ms |
14584 KB |
n=100 |
7 |
Correct |
16 ms |
14584 KB |
n=100 |
8 |
Correct |
15 ms |
14584 KB |
n=100 |
9 |
Correct |
18 ms |
14584 KB |
n=100 |
10 |
Correct |
15 ms |
14584 KB |
n=100 |
11 |
Correct |
21 ms |
14584 KB |
n=100 |
12 |
Correct |
14 ms |
14584 KB |
n=100 |
13 |
Correct |
15 ms |
14584 KB |
n=100 |
14 |
Correct |
18 ms |
14584 KB |
n=100 |
15 |
Correct |
15 ms |
14584 KB |
n=100 |
16 |
Correct |
15 ms |
14584 KB |
n=100 |
17 |
Correct |
15 ms |
14584 KB |
n=100 |
18 |
Correct |
14 ms |
14588 KB |
n=100 |
19 |
Correct |
15 ms |
14584 KB |
n=100 |
20 |
Correct |
15 ms |
14584 KB |
n=100 |
21 |
Correct |
15 ms |
14584 KB |
n=100 |
22 |
Correct |
15 ms |
14584 KB |
n=100 |
23 |
Correct |
15 ms |
14584 KB |
n=100 |
24 |
Correct |
15 ms |
14584 KB |
n=100 |
25 |
Correct |
15 ms |
14584 KB |
n=100 |
26 |
Correct |
15 ms |
14584 KB |
n=12 |
27 |
Correct |
15 ms |
14584 KB |
n=100 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
14712 KB |
n=5 |
2 |
Correct |
15 ms |
14584 KB |
n=100 |
3 |
Correct |
15 ms |
14584 KB |
n=100 |
4 |
Correct |
18 ms |
14584 KB |
n=100 |
5 |
Correct |
15 ms |
14584 KB |
n=100 |
6 |
Correct |
17 ms |
14584 KB |
n=100 |
7 |
Correct |
16 ms |
14584 KB |
n=100 |
8 |
Correct |
15 ms |
14584 KB |
n=100 |
9 |
Correct |
18 ms |
14584 KB |
n=100 |
10 |
Correct |
15 ms |
14584 KB |
n=100 |
11 |
Correct |
21 ms |
14584 KB |
n=100 |
12 |
Correct |
14 ms |
14584 KB |
n=100 |
13 |
Correct |
15 ms |
14584 KB |
n=100 |
14 |
Correct |
18 ms |
14584 KB |
n=100 |
15 |
Correct |
15 ms |
14584 KB |
n=100 |
16 |
Correct |
15 ms |
14584 KB |
n=100 |
17 |
Correct |
15 ms |
14584 KB |
n=100 |
18 |
Correct |
14 ms |
14588 KB |
n=100 |
19 |
Correct |
15 ms |
14584 KB |
n=100 |
20 |
Correct |
15 ms |
14584 KB |
n=100 |
21 |
Correct |
15 ms |
14584 KB |
n=100 |
22 |
Correct |
15 ms |
14584 KB |
n=100 |
23 |
Correct |
15 ms |
14584 KB |
n=100 |
24 |
Correct |
15 ms |
14584 KB |
n=100 |
25 |
Correct |
15 ms |
14584 KB |
n=100 |
26 |
Correct |
15 ms |
14584 KB |
n=12 |
27 |
Correct |
15 ms |
14584 KB |
n=100 |
28 |
Correct |
16 ms |
14756 KB |
n=500 |
29 |
Correct |
15 ms |
14712 KB |
n=500 |
30 |
Correct |
16 ms |
14712 KB |
n=500 |
31 |
Correct |
16 ms |
14712 KB |
n=500 |
32 |
Correct |
16 ms |
14712 KB |
n=500 |
33 |
Correct |
16 ms |
14716 KB |
n=500 |
34 |
Correct |
16 ms |
14712 KB |
n=500 |
35 |
Correct |
15 ms |
14716 KB |
n=500 |
36 |
Correct |
15 ms |
14712 KB |
n=500 |
37 |
Correct |
16 ms |
14712 KB |
n=500 |
38 |
Correct |
15 ms |
14712 KB |
n=500 |
39 |
Correct |
16 ms |
14712 KB |
n=500 |
40 |
Correct |
16 ms |
14712 KB |
n=500 |
41 |
Correct |
16 ms |
14716 KB |
n=500 |
42 |
Correct |
16 ms |
14712 KB |
n=500 |
43 |
Correct |
16 ms |
14712 KB |
n=500 |
44 |
Correct |
16 ms |
14712 KB |
n=500 |
45 |
Correct |
16 ms |
14712 KB |
n=500 |
46 |
Correct |
15 ms |
14712 KB |
n=500 |
47 |
Correct |
16 ms |
14712 KB |
n=500 |
48 |
Correct |
16 ms |
14712 KB |
n=500 |
49 |
Correct |
16 ms |
14712 KB |
n=500 |
50 |
Correct |
16 ms |
14712 KB |
n=500 |
51 |
Correct |
16 ms |
14712 KB |
n=500 |
52 |
Correct |
15 ms |
14712 KB |
n=500 |
53 |
Correct |
16 ms |
14712 KB |
n=500 |
54 |
Correct |
15 ms |
14712 KB |
n=500 |
55 |
Correct |
15 ms |
14584 KB |
n=278 |
56 |
Correct |
15 ms |
14712 KB |
n=500 |
57 |
Correct |
15 ms |
14712 KB |
n=500 |
58 |
Correct |
16 ms |
14712 KB |
n=500 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
14712 KB |
n=5 |
2 |
Correct |
15 ms |
14584 KB |
n=100 |
3 |
Correct |
15 ms |
14584 KB |
n=100 |
4 |
Correct |
18 ms |
14584 KB |
n=100 |
5 |
Correct |
15 ms |
14584 KB |
n=100 |
6 |
Correct |
17 ms |
14584 KB |
n=100 |
7 |
Correct |
16 ms |
14584 KB |
n=100 |
8 |
Correct |
15 ms |
14584 KB |
n=100 |
9 |
Correct |
18 ms |
14584 KB |
n=100 |
10 |
Correct |
15 ms |
14584 KB |
n=100 |
11 |
Correct |
21 ms |
14584 KB |
n=100 |
12 |
Correct |
14 ms |
14584 KB |
n=100 |
13 |
Correct |
15 ms |
14584 KB |
n=100 |
14 |
Correct |
18 ms |
14584 KB |
n=100 |
15 |
Correct |
15 ms |
14584 KB |
n=100 |
16 |
Correct |
15 ms |
14584 KB |
n=100 |
17 |
Correct |
15 ms |
14584 KB |
n=100 |
18 |
Correct |
14 ms |
14588 KB |
n=100 |
19 |
Correct |
15 ms |
14584 KB |
n=100 |
20 |
Correct |
15 ms |
14584 KB |
n=100 |
21 |
Correct |
15 ms |
14584 KB |
n=100 |
22 |
Correct |
15 ms |
14584 KB |
n=100 |
23 |
Correct |
15 ms |
14584 KB |
n=100 |
24 |
Correct |
15 ms |
14584 KB |
n=100 |
25 |
Correct |
15 ms |
14584 KB |
n=100 |
26 |
Correct |
15 ms |
14584 KB |
n=12 |
27 |
Correct |
15 ms |
14584 KB |
n=100 |
28 |
Correct |
16 ms |
14756 KB |
n=500 |
29 |
Correct |
15 ms |
14712 KB |
n=500 |
30 |
Correct |
16 ms |
14712 KB |
n=500 |
31 |
Correct |
16 ms |
14712 KB |
n=500 |
32 |
Correct |
16 ms |
14712 KB |
n=500 |
33 |
Correct |
16 ms |
14716 KB |
n=500 |
34 |
Correct |
16 ms |
14712 KB |
n=500 |
35 |
Correct |
15 ms |
14716 KB |
n=500 |
36 |
Correct |
15 ms |
14712 KB |
n=500 |
37 |
Correct |
16 ms |
14712 KB |
n=500 |
38 |
Correct |
15 ms |
14712 KB |
n=500 |
39 |
Correct |
16 ms |
14712 KB |
n=500 |
40 |
Correct |
16 ms |
14712 KB |
n=500 |
41 |
Correct |
16 ms |
14716 KB |
n=500 |
42 |
Correct |
16 ms |
14712 KB |
n=500 |
43 |
Correct |
16 ms |
14712 KB |
n=500 |
44 |
Correct |
16 ms |
14712 KB |
n=500 |
45 |
Correct |
16 ms |
14712 KB |
n=500 |
46 |
Correct |
15 ms |
14712 KB |
n=500 |
47 |
Correct |
16 ms |
14712 KB |
n=500 |
48 |
Correct |
16 ms |
14712 KB |
n=500 |
49 |
Correct |
16 ms |
14712 KB |
n=500 |
50 |
Correct |
16 ms |
14712 KB |
n=500 |
51 |
Correct |
16 ms |
14712 KB |
n=500 |
52 |
Correct |
15 ms |
14712 KB |
n=500 |
53 |
Correct |
16 ms |
14712 KB |
n=500 |
54 |
Correct |
15 ms |
14712 KB |
n=500 |
55 |
Correct |
15 ms |
14584 KB |
n=278 |
56 |
Correct |
15 ms |
14712 KB |
n=500 |
57 |
Correct |
15 ms |
14712 KB |
n=500 |
58 |
Correct |
16 ms |
14712 KB |
n=500 |
59 |
Correct |
21 ms |
15096 KB |
n=2000 |
60 |
Correct |
18 ms |
15096 KB |
n=2000 |
61 |
Correct |
18 ms |
15096 KB |
n=2000 |
62 |
Correct |
20 ms |
15096 KB |
n=2000 |
63 |
Correct |
21 ms |
15100 KB |
n=2000 |
64 |
Correct |
19 ms |
15096 KB |
n=2000 |
65 |
Correct |
20 ms |
15096 KB |
n=2000 |
66 |
Correct |
19 ms |
15096 KB |
n=2000 |
67 |
Correct |
21 ms |
15096 KB |
n=2000 |
68 |
Correct |
19 ms |
15096 KB |
n=2000 |
69 |
Correct |
18 ms |
15096 KB |
n=2000 |
70 |
Correct |
18 ms |
15096 KB |
n=2000 |
71 |
Correct |
19 ms |
15224 KB |
n=2000 |
72 |
Correct |
19 ms |
15096 KB |
n=2000 |
73 |
Correct |
22 ms |
15096 KB |
n=2000 |
74 |
Correct |
20 ms |
15096 KB |
n=1844 |
75 |
Correct |
19 ms |
15096 KB |
n=2000 |
76 |
Correct |
21 ms |
15100 KB |
n=2000 |
77 |
Correct |
21 ms |
15096 KB |
n=2000 |
78 |
Correct |
21 ms |
15096 KB |
n=2000 |
79 |
Correct |
20 ms |
15096 KB |
n=2000 |
80 |
Correct |
18 ms |
15096 KB |
n=2000 |
81 |
Correct |
19 ms |
15096 KB |
n=2000 |
82 |
Correct |
20 ms |
15068 KB |
n=2000 |
83 |
Correct |
19 ms |
15096 KB |
n=2000 |
84 |
Correct |
21 ms |
15096 KB |
n=2000 |
85 |
Correct |
20 ms |
15096 KB |
n=2000 |
86 |
Correct |
20 ms |
15096 KB |
n=2000 |
87 |
Correct |
21 ms |
15096 KB |
n=2000 |
88 |
Correct |
18 ms |
15100 KB |
n=2000 |
89 |
Correct |
19 ms |
15144 KB |
n=2000 |
90 |
Correct |
19 ms |
15224 KB |
n=2000 |
91 |
Correct |
26 ms |
15096 KB |
n=2000 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
14712 KB |
n=5 |
2 |
Correct |
15 ms |
14584 KB |
n=100 |
3 |
Correct |
15 ms |
14584 KB |
n=100 |
4 |
Correct |
18 ms |
14584 KB |
n=100 |
5 |
Correct |
15 ms |
14584 KB |
n=100 |
6 |
Correct |
17 ms |
14584 KB |
n=100 |
7 |
Correct |
16 ms |
14584 KB |
n=100 |
8 |
Correct |
15 ms |
14584 KB |
n=100 |
9 |
Correct |
18 ms |
14584 KB |
n=100 |
10 |
Correct |
15 ms |
14584 KB |
n=100 |
11 |
Correct |
21 ms |
14584 KB |
n=100 |
12 |
Correct |
14 ms |
14584 KB |
n=100 |
13 |
Correct |
15 ms |
14584 KB |
n=100 |
14 |
Correct |
18 ms |
14584 KB |
n=100 |
15 |
Correct |
15 ms |
14584 KB |
n=100 |
16 |
Correct |
15 ms |
14584 KB |
n=100 |
17 |
Correct |
15 ms |
14584 KB |
n=100 |
18 |
Correct |
14 ms |
14588 KB |
n=100 |
19 |
Correct |
15 ms |
14584 KB |
n=100 |
20 |
Correct |
15 ms |
14584 KB |
n=100 |
21 |
Correct |
15 ms |
14584 KB |
n=100 |
22 |
Correct |
15 ms |
14584 KB |
n=100 |
23 |
Correct |
15 ms |
14584 KB |
n=100 |
24 |
Correct |
15 ms |
14584 KB |
n=100 |
25 |
Correct |
15 ms |
14584 KB |
n=100 |
26 |
Correct |
15 ms |
14584 KB |
n=12 |
27 |
Correct |
15 ms |
14584 KB |
n=100 |
28 |
Correct |
16 ms |
14756 KB |
n=500 |
29 |
Correct |
15 ms |
14712 KB |
n=500 |
30 |
Correct |
16 ms |
14712 KB |
n=500 |
31 |
Correct |
16 ms |
14712 KB |
n=500 |
32 |
Correct |
16 ms |
14712 KB |
n=500 |
33 |
Correct |
16 ms |
14716 KB |
n=500 |
34 |
Correct |
16 ms |
14712 KB |
n=500 |
35 |
Correct |
15 ms |
14716 KB |
n=500 |
36 |
Correct |
15 ms |
14712 KB |
n=500 |
37 |
Correct |
16 ms |
14712 KB |
n=500 |
38 |
Correct |
15 ms |
14712 KB |
n=500 |
39 |
Correct |
16 ms |
14712 KB |
n=500 |
40 |
Correct |
16 ms |
14712 KB |
n=500 |
41 |
Correct |
16 ms |
14716 KB |
n=500 |
42 |
Correct |
16 ms |
14712 KB |
n=500 |
43 |
Correct |
16 ms |
14712 KB |
n=500 |
44 |
Correct |
16 ms |
14712 KB |
n=500 |
45 |
Correct |
16 ms |
14712 KB |
n=500 |
46 |
Correct |
15 ms |
14712 KB |
n=500 |
47 |
Correct |
16 ms |
14712 KB |
n=500 |
48 |
Correct |
16 ms |
14712 KB |
n=500 |
49 |
Correct |
16 ms |
14712 KB |
n=500 |
50 |
Correct |
16 ms |
14712 KB |
n=500 |
51 |
Correct |
16 ms |
14712 KB |
n=500 |
52 |
Correct |
15 ms |
14712 KB |
n=500 |
53 |
Correct |
16 ms |
14712 KB |
n=500 |
54 |
Correct |
15 ms |
14712 KB |
n=500 |
55 |
Correct |
15 ms |
14584 KB |
n=278 |
56 |
Correct |
15 ms |
14712 KB |
n=500 |
57 |
Correct |
15 ms |
14712 KB |
n=500 |
58 |
Correct |
16 ms |
14712 KB |
n=500 |
59 |
Correct |
21 ms |
15096 KB |
n=2000 |
60 |
Correct |
18 ms |
15096 KB |
n=2000 |
61 |
Correct |
18 ms |
15096 KB |
n=2000 |
62 |
Correct |
20 ms |
15096 KB |
n=2000 |
63 |
Correct |
21 ms |
15100 KB |
n=2000 |
64 |
Correct |
19 ms |
15096 KB |
n=2000 |
65 |
Correct |
20 ms |
15096 KB |
n=2000 |
66 |
Correct |
19 ms |
15096 KB |
n=2000 |
67 |
Correct |
21 ms |
15096 KB |
n=2000 |
68 |
Correct |
19 ms |
15096 KB |
n=2000 |
69 |
Correct |
18 ms |
15096 KB |
n=2000 |
70 |
Correct |
18 ms |
15096 KB |
n=2000 |
71 |
Correct |
19 ms |
15224 KB |
n=2000 |
72 |
Correct |
19 ms |
15096 KB |
n=2000 |
73 |
Correct |
22 ms |
15096 KB |
n=2000 |
74 |
Correct |
20 ms |
15096 KB |
n=1844 |
75 |
Correct |
19 ms |
15096 KB |
n=2000 |
76 |
Correct |
21 ms |
15100 KB |
n=2000 |
77 |
Correct |
21 ms |
15096 KB |
n=2000 |
78 |
Correct |
21 ms |
15096 KB |
n=2000 |
79 |
Correct |
20 ms |
15096 KB |
n=2000 |
80 |
Correct |
18 ms |
15096 KB |
n=2000 |
81 |
Correct |
19 ms |
15096 KB |
n=2000 |
82 |
Correct |
20 ms |
15068 KB |
n=2000 |
83 |
Correct |
19 ms |
15096 KB |
n=2000 |
84 |
Correct |
21 ms |
15096 KB |
n=2000 |
85 |
Correct |
20 ms |
15096 KB |
n=2000 |
86 |
Correct |
20 ms |
15096 KB |
n=2000 |
87 |
Correct |
21 ms |
15096 KB |
n=2000 |
88 |
Correct |
18 ms |
15100 KB |
n=2000 |
89 |
Correct |
19 ms |
15144 KB |
n=2000 |
90 |
Correct |
19 ms |
15224 KB |
n=2000 |
91 |
Correct |
26 ms |
15096 KB |
n=2000 |
92 |
Correct |
2152 ms |
66260 KB |
n=200000 |
93 |
Correct |
1339 ms |
71160 KB |
n=200000 |
94 |
Correct |
900 ms |
74380 KB |
n=200000 |
95 |
Correct |
2064 ms |
66132 KB |
n=200000 |
96 |
Correct |
2117 ms |
65932 KB |
n=200000 |
97 |
Correct |
1574 ms |
70236 KB |
n=200000 |
98 |
Correct |
2159 ms |
66028 KB |
n=200000 |
99 |
Correct |
2055 ms |
66168 KB |
n=200000 |
100 |
Correct |
2059 ms |
66012 KB |
n=200000 |
101 |
Correct |
658 ms |
75768 KB |
n=200000 |
102 |
Correct |
877 ms |
67040 KB |
n=200000 |
103 |
Correct |
881 ms |
67192 KB |
n=200000 |
104 |
Correct |
884 ms |
67320 KB |
n=200000 |
105 |
Correct |
940 ms |
67556 KB |
n=200000 |
106 |
Correct |
972 ms |
67696 KB |
n=200000 |
107 |
Correct |
879 ms |
67576 KB |
n=200000 |
108 |
Correct |
1814 ms |
66152 KB |
n=200000 |
109 |
Correct |
1823 ms |
66072 KB |
n=200000 |
110 |
Correct |
1810 ms |
65912 KB |
n=200000 |
111 |
Correct |
1708 ms |
65484 KB |
n=200000 |
112 |
Correct |
775 ms |
74472 KB |
n=200000 |
113 |
Correct |
1410 ms |
69996 KB |
n=200000 |
114 |
Correct |
1744 ms |
65492 KB |
n=200000 |
115 |
Correct |
2291 ms |
67976 KB |
n=200000 |
116 |
Correct |
1957 ms |
66292 KB |
n=200000 |
117 |
Correct |
720 ms |
74844 KB |
n=200000 |
118 |
Correct |
1687 ms |
68952 KB |
n=200000 |
119 |
Correct |
1908 ms |
66184 KB |
n=200000 |
120 |
Correct |
615 ms |
74596 KB |
n=200000 |
121 |
Correct |
623 ms |
74648 KB |
n=200000 |
122 |
Correct |
583 ms |
75008 KB |
n=200000 |
123 |
Correct |
942 ms |
67340 KB |
n=200000 |
124 |
Correct |
214 ms |
29560 KB |
n=25264 |