#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
const int N = 200005, M = 18;
vector<int> v[N];
set<int> s[N], o[N];
int a[N], b[N], d[N], up[N][M];
void dfsu(int x = 1, int y = 0) {
up[x][0] = y;
d[x] = d[y] + 1;
for(int z : v[x]) {
if(z == y) continue;
dfsu(z, x);
}
}
int L(int x, int y) {
if(!x || !y) return 0;
if(d[x] < d[y]) swap(x, y);
for(int i = M - 1; i >= 0; --i) {
if(d[x] - (1 << i) >= d[y]) {
x = up[x][i];
}
}
if(x == y) return x;
for(int i = M - 1; i >= 0; --i) {
if(up[x][i] ^ up[y][i]) {
x = up[x][i];
y = up[y][i];
}
}
return up[x][0];
}
void _set(int i, int x) {
if(b[i - 1]) s[b[i - 1]].erase(i - 1);
if(b[i]) s[b[i]].erase(i);
if(a[i]) o[a[i]].erase(i);
a[i] = x;
if(a[i]) o[a[i]].insert(i);
b[i - 1] = L(a[i - 1], a[i]);
b[i] = L(a[i], a[i + 1]);
if(b[i - 1]) s[b[i - 1]].insert(i - 1);
if(b[i]) s[b[i]].insert(i);
}
void answer(int l, int r, int x) {
auto it = o[x].lower_bound(l);
if(it != o[x].end() && *it <= r) {
cout << *it << " " << *it << "\n";
return;
}
it = s[x].lower_bound(l);
if(it != s[x].end() && *it <= r - 1) {
cout << *it << " " << *it + 1 << "\n";
return;
}
cout << "-1 -1\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef x
freopen("x.txt", "r", stdin);
#endif
int n, m, q;
cin >> n >> m >> q;
for(int i = 1; i < n; ++i) {
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfsu();
for(int i = 1; i < M; ++i) {
for(int j = 1; j <= n; ++j) {
up[j][i] = up[up[j][i - 1]][i - 1];
}
}
for(int i = 1; i <= m; ++i) {
int x;
cin >> x;
_set(i, x);
}
for(int i = 1; i <= q; ++i) {
int t, x, y;
cin >> t >> x >> y;
if(t == 1) {
_set(x, y);
} else {
int z;
cin >> z;
answer(x, y, z);
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23756 KB |
n=5 |
2 |
Correct |
14 ms |
23740 KB |
n=100 |
3 |
Correct |
11 ms |
23756 KB |
n=100 |
4 |
Correct |
12 ms |
23792 KB |
n=100 |
5 |
Correct |
12 ms |
23808 KB |
n=100 |
6 |
Correct |
13 ms |
23756 KB |
n=100 |
7 |
Correct |
12 ms |
23756 KB |
n=100 |
8 |
Correct |
12 ms |
23776 KB |
n=100 |
9 |
Correct |
13 ms |
23772 KB |
n=100 |
10 |
Correct |
12 ms |
23804 KB |
n=100 |
11 |
Correct |
13 ms |
23816 KB |
n=100 |
12 |
Correct |
12 ms |
23756 KB |
n=100 |
13 |
Correct |
12 ms |
23756 KB |
n=100 |
14 |
Correct |
12 ms |
23756 KB |
n=100 |
15 |
Correct |
12 ms |
23756 KB |
n=100 |
16 |
Correct |
12 ms |
23796 KB |
n=100 |
17 |
Correct |
11 ms |
23788 KB |
n=100 |
18 |
Correct |
14 ms |
23800 KB |
n=100 |
19 |
Correct |
12 ms |
23756 KB |
n=100 |
20 |
Correct |
12 ms |
23756 KB |
n=100 |
21 |
Correct |
13 ms |
23780 KB |
n=100 |
22 |
Correct |
12 ms |
23756 KB |
n=100 |
23 |
Correct |
15 ms |
23756 KB |
n=100 |
24 |
Correct |
12 ms |
23756 KB |
n=100 |
25 |
Correct |
11 ms |
23800 KB |
n=100 |
26 |
Correct |
14 ms |
23756 KB |
n=12 |
27 |
Correct |
12 ms |
23800 KB |
n=100 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23756 KB |
n=5 |
2 |
Correct |
14 ms |
23740 KB |
n=100 |
3 |
Correct |
11 ms |
23756 KB |
n=100 |
4 |
Correct |
12 ms |
23792 KB |
n=100 |
5 |
Correct |
12 ms |
23808 KB |
n=100 |
6 |
Correct |
13 ms |
23756 KB |
n=100 |
7 |
Correct |
12 ms |
23756 KB |
n=100 |
8 |
Correct |
12 ms |
23776 KB |
n=100 |
9 |
Correct |
13 ms |
23772 KB |
n=100 |
10 |
Correct |
12 ms |
23804 KB |
n=100 |
11 |
Correct |
13 ms |
23816 KB |
n=100 |
12 |
Correct |
12 ms |
23756 KB |
n=100 |
13 |
Correct |
12 ms |
23756 KB |
n=100 |
14 |
Correct |
12 ms |
23756 KB |
n=100 |
15 |
Correct |
12 ms |
23756 KB |
n=100 |
16 |
Correct |
12 ms |
23796 KB |
n=100 |
17 |
Correct |
11 ms |
23788 KB |
n=100 |
18 |
Correct |
14 ms |
23800 KB |
n=100 |
19 |
Correct |
12 ms |
23756 KB |
n=100 |
20 |
Correct |
12 ms |
23756 KB |
n=100 |
21 |
Correct |
13 ms |
23780 KB |
n=100 |
22 |
Correct |
12 ms |
23756 KB |
n=100 |
23 |
Correct |
15 ms |
23756 KB |
n=100 |
24 |
Correct |
12 ms |
23756 KB |
n=100 |
25 |
Correct |
11 ms |
23800 KB |
n=100 |
26 |
Correct |
14 ms |
23756 KB |
n=12 |
27 |
Correct |
12 ms |
23800 KB |
n=100 |
28 |
Correct |
12 ms |
23884 KB |
n=500 |
29 |
Correct |
15 ms |
23916 KB |
n=500 |
30 |
Correct |
13 ms |
23944 KB |
n=500 |
31 |
Correct |
13 ms |
23884 KB |
n=500 |
32 |
Correct |
12 ms |
23812 KB |
n=500 |
33 |
Correct |
12 ms |
23912 KB |
n=500 |
34 |
Correct |
12 ms |
23936 KB |
n=500 |
35 |
Correct |
12 ms |
23884 KB |
n=500 |
36 |
Correct |
13 ms |
23884 KB |
n=500 |
37 |
Correct |
15 ms |
23884 KB |
n=500 |
38 |
Correct |
13 ms |
23884 KB |
n=500 |
39 |
Correct |
13 ms |
23808 KB |
n=500 |
40 |
Correct |
13 ms |
23944 KB |
n=500 |
41 |
Correct |
13 ms |
23940 KB |
n=500 |
42 |
Correct |
13 ms |
23884 KB |
n=500 |
43 |
Correct |
13 ms |
23884 KB |
n=500 |
44 |
Correct |
12 ms |
23884 KB |
n=500 |
45 |
Correct |
13 ms |
23884 KB |
n=500 |
46 |
Correct |
12 ms |
23884 KB |
n=500 |
47 |
Correct |
13 ms |
23952 KB |
n=500 |
48 |
Correct |
13 ms |
23884 KB |
n=500 |
49 |
Correct |
12 ms |
23884 KB |
n=500 |
50 |
Correct |
14 ms |
23936 KB |
n=500 |
51 |
Correct |
12 ms |
23852 KB |
n=500 |
52 |
Correct |
14 ms |
23904 KB |
n=500 |
53 |
Correct |
18 ms |
23808 KB |
n=500 |
54 |
Correct |
12 ms |
23884 KB |
n=500 |
55 |
Correct |
12 ms |
23864 KB |
n=278 |
56 |
Correct |
12 ms |
23940 KB |
n=500 |
57 |
Correct |
12 ms |
23884 KB |
n=500 |
58 |
Correct |
12 ms |
23884 KB |
n=500 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23756 KB |
n=5 |
2 |
Correct |
14 ms |
23740 KB |
n=100 |
3 |
Correct |
11 ms |
23756 KB |
n=100 |
4 |
Correct |
12 ms |
23792 KB |
n=100 |
5 |
Correct |
12 ms |
23808 KB |
n=100 |
6 |
Correct |
13 ms |
23756 KB |
n=100 |
7 |
Correct |
12 ms |
23756 KB |
n=100 |
8 |
Correct |
12 ms |
23776 KB |
n=100 |
9 |
Correct |
13 ms |
23772 KB |
n=100 |
10 |
Correct |
12 ms |
23804 KB |
n=100 |
11 |
Correct |
13 ms |
23816 KB |
n=100 |
12 |
Correct |
12 ms |
23756 KB |
n=100 |
13 |
Correct |
12 ms |
23756 KB |
n=100 |
14 |
Correct |
12 ms |
23756 KB |
n=100 |
15 |
Correct |
12 ms |
23756 KB |
n=100 |
16 |
Correct |
12 ms |
23796 KB |
n=100 |
17 |
Correct |
11 ms |
23788 KB |
n=100 |
18 |
Correct |
14 ms |
23800 KB |
n=100 |
19 |
Correct |
12 ms |
23756 KB |
n=100 |
20 |
Correct |
12 ms |
23756 KB |
n=100 |
21 |
Correct |
13 ms |
23780 KB |
n=100 |
22 |
Correct |
12 ms |
23756 KB |
n=100 |
23 |
Correct |
15 ms |
23756 KB |
n=100 |
24 |
Correct |
12 ms |
23756 KB |
n=100 |
25 |
Correct |
11 ms |
23800 KB |
n=100 |
26 |
Correct |
14 ms |
23756 KB |
n=12 |
27 |
Correct |
12 ms |
23800 KB |
n=100 |
28 |
Correct |
12 ms |
23884 KB |
n=500 |
29 |
Correct |
15 ms |
23916 KB |
n=500 |
30 |
Correct |
13 ms |
23944 KB |
n=500 |
31 |
Correct |
13 ms |
23884 KB |
n=500 |
32 |
Correct |
12 ms |
23812 KB |
n=500 |
33 |
Correct |
12 ms |
23912 KB |
n=500 |
34 |
Correct |
12 ms |
23936 KB |
n=500 |
35 |
Correct |
12 ms |
23884 KB |
n=500 |
36 |
Correct |
13 ms |
23884 KB |
n=500 |
37 |
Correct |
15 ms |
23884 KB |
n=500 |
38 |
Correct |
13 ms |
23884 KB |
n=500 |
39 |
Correct |
13 ms |
23808 KB |
n=500 |
40 |
Correct |
13 ms |
23944 KB |
n=500 |
41 |
Correct |
13 ms |
23940 KB |
n=500 |
42 |
Correct |
13 ms |
23884 KB |
n=500 |
43 |
Correct |
13 ms |
23884 KB |
n=500 |
44 |
Correct |
12 ms |
23884 KB |
n=500 |
45 |
Correct |
13 ms |
23884 KB |
n=500 |
46 |
Correct |
12 ms |
23884 KB |
n=500 |
47 |
Correct |
13 ms |
23952 KB |
n=500 |
48 |
Correct |
13 ms |
23884 KB |
n=500 |
49 |
Correct |
12 ms |
23884 KB |
n=500 |
50 |
Correct |
14 ms |
23936 KB |
n=500 |
51 |
Correct |
12 ms |
23852 KB |
n=500 |
52 |
Correct |
14 ms |
23904 KB |
n=500 |
53 |
Correct |
18 ms |
23808 KB |
n=500 |
54 |
Correct |
12 ms |
23884 KB |
n=500 |
55 |
Correct |
12 ms |
23864 KB |
n=278 |
56 |
Correct |
12 ms |
23940 KB |
n=500 |
57 |
Correct |
12 ms |
23884 KB |
n=500 |
58 |
Correct |
12 ms |
23884 KB |
n=500 |
59 |
Correct |
15 ms |
24304 KB |
n=2000 |
60 |
Correct |
15 ms |
24396 KB |
n=2000 |
61 |
Correct |
15 ms |
24348 KB |
n=2000 |
62 |
Correct |
17 ms |
24272 KB |
n=2000 |
63 |
Correct |
15 ms |
24280 KB |
n=2000 |
64 |
Correct |
14 ms |
24268 KB |
n=2000 |
65 |
Correct |
14 ms |
24268 KB |
n=2000 |
66 |
Correct |
15 ms |
24464 KB |
n=2000 |
67 |
Correct |
18 ms |
24268 KB |
n=2000 |
68 |
Correct |
15 ms |
24324 KB |
n=2000 |
69 |
Correct |
14 ms |
24268 KB |
n=2000 |
70 |
Correct |
19 ms |
24292 KB |
n=2000 |
71 |
Correct |
16 ms |
24196 KB |
n=2000 |
72 |
Correct |
14 ms |
24200 KB |
n=2000 |
73 |
Correct |
14 ms |
24268 KB |
n=2000 |
74 |
Correct |
15 ms |
24268 KB |
n=1844 |
75 |
Correct |
13 ms |
24196 KB |
n=2000 |
76 |
Correct |
16 ms |
24208 KB |
n=2000 |
77 |
Correct |
20 ms |
24252 KB |
n=2000 |
78 |
Correct |
16 ms |
24268 KB |
n=2000 |
79 |
Correct |
15 ms |
24200 KB |
n=2000 |
80 |
Correct |
14 ms |
24268 KB |
n=2000 |
81 |
Correct |
15 ms |
24324 KB |
n=2000 |
82 |
Correct |
14 ms |
24280 KB |
n=2000 |
83 |
Correct |
16 ms |
24328 KB |
n=2000 |
84 |
Correct |
15 ms |
24296 KB |
n=2000 |
85 |
Correct |
16 ms |
24284 KB |
n=2000 |
86 |
Correct |
19 ms |
24188 KB |
n=2000 |
87 |
Correct |
15 ms |
24268 KB |
n=2000 |
88 |
Correct |
14 ms |
24268 KB |
n=2000 |
89 |
Correct |
15 ms |
24380 KB |
n=2000 |
90 |
Correct |
14 ms |
24280 KB |
n=2000 |
91 |
Correct |
14 ms |
24268 KB |
n=2000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23756 KB |
n=5 |
2 |
Correct |
14 ms |
23740 KB |
n=100 |
3 |
Correct |
11 ms |
23756 KB |
n=100 |
4 |
Correct |
12 ms |
23792 KB |
n=100 |
5 |
Correct |
12 ms |
23808 KB |
n=100 |
6 |
Correct |
13 ms |
23756 KB |
n=100 |
7 |
Correct |
12 ms |
23756 KB |
n=100 |
8 |
Correct |
12 ms |
23776 KB |
n=100 |
9 |
Correct |
13 ms |
23772 KB |
n=100 |
10 |
Correct |
12 ms |
23804 KB |
n=100 |
11 |
Correct |
13 ms |
23816 KB |
n=100 |
12 |
Correct |
12 ms |
23756 KB |
n=100 |
13 |
Correct |
12 ms |
23756 KB |
n=100 |
14 |
Correct |
12 ms |
23756 KB |
n=100 |
15 |
Correct |
12 ms |
23756 KB |
n=100 |
16 |
Correct |
12 ms |
23796 KB |
n=100 |
17 |
Correct |
11 ms |
23788 KB |
n=100 |
18 |
Correct |
14 ms |
23800 KB |
n=100 |
19 |
Correct |
12 ms |
23756 KB |
n=100 |
20 |
Correct |
12 ms |
23756 KB |
n=100 |
21 |
Correct |
13 ms |
23780 KB |
n=100 |
22 |
Correct |
12 ms |
23756 KB |
n=100 |
23 |
Correct |
15 ms |
23756 KB |
n=100 |
24 |
Correct |
12 ms |
23756 KB |
n=100 |
25 |
Correct |
11 ms |
23800 KB |
n=100 |
26 |
Correct |
14 ms |
23756 KB |
n=12 |
27 |
Correct |
12 ms |
23800 KB |
n=100 |
28 |
Correct |
12 ms |
23884 KB |
n=500 |
29 |
Correct |
15 ms |
23916 KB |
n=500 |
30 |
Correct |
13 ms |
23944 KB |
n=500 |
31 |
Correct |
13 ms |
23884 KB |
n=500 |
32 |
Correct |
12 ms |
23812 KB |
n=500 |
33 |
Correct |
12 ms |
23912 KB |
n=500 |
34 |
Correct |
12 ms |
23936 KB |
n=500 |
35 |
Correct |
12 ms |
23884 KB |
n=500 |
36 |
Correct |
13 ms |
23884 KB |
n=500 |
37 |
Correct |
15 ms |
23884 KB |
n=500 |
38 |
Correct |
13 ms |
23884 KB |
n=500 |
39 |
Correct |
13 ms |
23808 KB |
n=500 |
40 |
Correct |
13 ms |
23944 KB |
n=500 |
41 |
Correct |
13 ms |
23940 KB |
n=500 |
42 |
Correct |
13 ms |
23884 KB |
n=500 |
43 |
Correct |
13 ms |
23884 KB |
n=500 |
44 |
Correct |
12 ms |
23884 KB |
n=500 |
45 |
Correct |
13 ms |
23884 KB |
n=500 |
46 |
Correct |
12 ms |
23884 KB |
n=500 |
47 |
Correct |
13 ms |
23952 KB |
n=500 |
48 |
Correct |
13 ms |
23884 KB |
n=500 |
49 |
Correct |
12 ms |
23884 KB |
n=500 |
50 |
Correct |
14 ms |
23936 KB |
n=500 |
51 |
Correct |
12 ms |
23852 KB |
n=500 |
52 |
Correct |
14 ms |
23904 KB |
n=500 |
53 |
Correct |
18 ms |
23808 KB |
n=500 |
54 |
Correct |
12 ms |
23884 KB |
n=500 |
55 |
Correct |
12 ms |
23864 KB |
n=278 |
56 |
Correct |
12 ms |
23940 KB |
n=500 |
57 |
Correct |
12 ms |
23884 KB |
n=500 |
58 |
Correct |
12 ms |
23884 KB |
n=500 |
59 |
Correct |
15 ms |
24304 KB |
n=2000 |
60 |
Correct |
15 ms |
24396 KB |
n=2000 |
61 |
Correct |
15 ms |
24348 KB |
n=2000 |
62 |
Correct |
17 ms |
24272 KB |
n=2000 |
63 |
Correct |
15 ms |
24280 KB |
n=2000 |
64 |
Correct |
14 ms |
24268 KB |
n=2000 |
65 |
Correct |
14 ms |
24268 KB |
n=2000 |
66 |
Correct |
15 ms |
24464 KB |
n=2000 |
67 |
Correct |
18 ms |
24268 KB |
n=2000 |
68 |
Correct |
15 ms |
24324 KB |
n=2000 |
69 |
Correct |
14 ms |
24268 KB |
n=2000 |
70 |
Correct |
19 ms |
24292 KB |
n=2000 |
71 |
Correct |
16 ms |
24196 KB |
n=2000 |
72 |
Correct |
14 ms |
24200 KB |
n=2000 |
73 |
Correct |
14 ms |
24268 KB |
n=2000 |
74 |
Correct |
15 ms |
24268 KB |
n=1844 |
75 |
Correct |
13 ms |
24196 KB |
n=2000 |
76 |
Correct |
16 ms |
24208 KB |
n=2000 |
77 |
Correct |
20 ms |
24252 KB |
n=2000 |
78 |
Correct |
16 ms |
24268 KB |
n=2000 |
79 |
Correct |
15 ms |
24200 KB |
n=2000 |
80 |
Correct |
14 ms |
24268 KB |
n=2000 |
81 |
Correct |
15 ms |
24324 KB |
n=2000 |
82 |
Correct |
14 ms |
24280 KB |
n=2000 |
83 |
Correct |
16 ms |
24328 KB |
n=2000 |
84 |
Correct |
15 ms |
24296 KB |
n=2000 |
85 |
Correct |
16 ms |
24284 KB |
n=2000 |
86 |
Correct |
19 ms |
24188 KB |
n=2000 |
87 |
Correct |
15 ms |
24268 KB |
n=2000 |
88 |
Correct |
14 ms |
24268 KB |
n=2000 |
89 |
Correct |
15 ms |
24380 KB |
n=2000 |
90 |
Correct |
14 ms |
24280 KB |
n=2000 |
91 |
Correct |
14 ms |
24268 KB |
n=2000 |
92 |
Correct |
625 ms |
72484 KB |
n=200000 |
93 |
Correct |
820 ms |
76176 KB |
n=200000 |
94 |
Correct |
774 ms |
79644 KB |
n=200000 |
95 |
Correct |
653 ms |
72300 KB |
n=200000 |
96 |
Correct |
587 ms |
72380 KB |
n=200000 |
97 |
Correct |
832 ms |
75420 KB |
n=200000 |
98 |
Correct |
646 ms |
72572 KB |
n=200000 |
99 |
Correct |
735 ms |
71784 KB |
n=200000 |
100 |
Correct |
671 ms |
72184 KB |
n=200000 |
101 |
Correct |
732 ms |
80156 KB |
n=200000 |
102 |
Correct |
390 ms |
73140 KB |
n=200000 |
103 |
Correct |
404 ms |
73184 KB |
n=200000 |
104 |
Correct |
389 ms |
72888 KB |
n=200000 |
105 |
Correct |
405 ms |
73028 KB |
n=200000 |
106 |
Correct |
398 ms |
73012 KB |
n=200000 |
107 |
Correct |
399 ms |
72988 KB |
n=200000 |
108 |
Correct |
708 ms |
71876 KB |
n=200000 |
109 |
Correct |
700 ms |
71888 KB |
n=200000 |
110 |
Correct |
706 ms |
71816 KB |
n=200000 |
111 |
Correct |
654 ms |
72004 KB |
n=200000 |
112 |
Correct |
763 ms |
79496 KB |
n=200000 |
113 |
Correct |
876 ms |
75060 KB |
n=200000 |
114 |
Correct |
660 ms |
72028 KB |
n=200000 |
115 |
Correct |
926 ms |
72924 KB |
n=200000 |
116 |
Correct |
617 ms |
71868 KB |
n=200000 |
117 |
Correct |
753 ms |
79780 KB |
n=200000 |
118 |
Correct |
975 ms |
73756 KB |
n=200000 |
119 |
Correct |
666 ms |
71728 KB |
n=200000 |
120 |
Correct |
722 ms |
80116 KB |
n=200000 |
121 |
Correct |
764 ms |
79992 KB |
n=200000 |
122 |
Correct |
699 ms |
80580 KB |
n=200000 |
123 |
Correct |
422 ms |
72136 KB |
n=200000 |
124 |
Correct |
178 ms |
38844 KB |
n=25264 |