#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, q, a[N], h[N], par[20][N], st[N], en[N], cnt = 0;
vector <int> g[N];
void dfs (int u, int p) {
st[u] = ++cnt;
for (auto v: g[u]) {
if (v == p) continue;
h[v] = h[u] + 1;
par[0][v] = u;
dfs(v, u);
}
en[u] = cnt;
}
void makeLCA(){
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n; j++) {
if (par[i - 1][j] != -1) par[i][j] = par[i - 1][par[i - 1][j]];
}
}
}
int LCA (int x, int y) {
if (x == 0) return y;
if (y == 0) return x;
if (h[x] > h[y]) swap(x, y);
for (int i = 19; i >= 0; i--) if (par[i][y] != -1 && h[y] - (1 << i) >= h[x]) y = par[i][y];
if (x == y) return x;
for (int i = 19; i >= 0; i--) {
if (par[i][x] != -1 && par[i][y] != -1 && par[i][x] != par[i][y]) {
x = par[i][x];
y = par[i][y];
}
}
if (x == y) return x;
return par[0][x];
}
struct LCAIT {
int node[N << 2];
void init (int i, int l, int r) {
if (l == r) {
node[i] = a[l];
return;
}
int mid = l + r >> 1;
init(i << 1, l, mid);
init(i << 1 | 1, mid + 1, r);
node[i] = LCA(node[i << 1], node[i << 1 | 1]);
}
void update (int i, int l, int r, int pos, int val) {
if (l == r) {
node[i] = val;
return;
}
int mid = l + r >> 1;
if (pos <= mid) update(i << 1, l, mid, pos, val);
else update(i << 1 | 1, mid + 1, r, pos, val);
node[i] = LCA(node[i << 1], node[i << 1 | 1]);
}
int query (int i, int l, int r, int a, int b) {
if (l > r || a > r || b < l) return 0;
if (a <= l && r <= b) return node[i];
int mid = l + r >> 1;
return LCA(query(i << 1, l, mid, a, b), query(i << 1 | 1, mid + 1, r, a, b));
}
} lcait;
struct ProneIT {
struct Node {
int Min, Max;
Node (int Min = 0, int Max = 0): Min(Min), Max(Max) {}
Node operator + (const Node &rhs) const {
return Node(min(Min, rhs.Min), max(Max, rhs.Max));
}
} node[N << 2];
void init (int i, int l, int r) {
if (l == r) {
node[i] = Node(st[a[l]], st[a[l]]);
return;
}
int mid = l + r >> 1;
init(i << 1, l, mid);
init(i << 1 | 1, mid + 1, r);
node[i] = node[i << 1] + node[i << 1 | 1];
}
void update (int i, int l, int r, int pos, int val) {
if (l == r) {
node[i] = Node(st[val], st[val]);
return;
}
int mid = l + r >> 1;
update(i << 1, l, mid, pos, val);
update(i << 1 | 1, mid + 1, r, pos, val);
node[i] = node[i << 1] + node[i << 1 | 1];
}
Node query (int i, int l, int r, int a, int b) {
if (l > r || a > r || b < l) return Node(1e9, -1e9);
if (a <= l && r <= b) return node[i];
int mid = l + r >> 1;
return query(i << 1, l, mid, a, b) + query(i << 1 | 1, mid + 1, r, a, b);
}
int prone_max_left (int i, int l, int r, int a, int b, int val) {
if (l > r || a > r || b < l) return -1;
if (a <= l && r <= b) {
if (node[i].Max <= val) return l;
}
if (l == r) {
if (node[i].Max <= val) return l;
return -1;
}
int mid = l + r >> 1;
int cur = prone_max_left(i << 1, l, mid, a, b, val);
if (cur != -1) return cur;
return prone_max_left(i << 1 | 1, mid + 1, r, a, b, val);
}
int prone_min_left (int i, int l, int r, int a, int b, int val) {
if (l > r || a > r || b < l) return -1;
if (a <= l && r <= b) {
if (node[i].Min >= val) return l;
}
if (l == r) {
if (node[i].Min >= val) return l;
return -1;
}
int mid = l + r >> 1;
int cur = prone_min_left(i << 1, l, mid, a, b, val);
if (cur != -1) return cur;
return prone_min_left(i << 1 | 1, mid + 1, r, a, b, val);
}
int prone_max_right (int i, int l, int r, int a, int b, int val) {
if (l > r || a > r || b < l) return -1;
if (a <= l && r <= b) {
if (node[i].Max <= val) return l;
}
if (l == r) {
if (node[i].Max <= val) return l;
return -1;
}
int mid = l + r >> 1;
int cur = prone_max_right(i << 1 | 1, mid + 1, r, a, b, val);
if (cur != -1) return cur;
return prone_max_right(i << 1, l, mid, a, b, val);
}
int prone_min_right (int i, int l, int r, int a, int b, int val) {
if (l > r || a > r || b < l) return -1;
if (a <= l && r <= b) {
if (node[i].Min >= val) return l;
}
if (l == r) {
if (node[i].Min >= val) return l;
return -1;
}
int mid = l + r >> 1;
int cur = prone_min_right(i << 1 | 1, mid + 1, r, a, b, val);
if (cur != -1) return cur;
return prone_min_right(i << 1, l, mid, a, b, val);
}
pair <int, pair <int, int> > solve (int i, int l, int r, int a, int b, int v) {
if (l > r || a > r || b < l) return {-1, {-1, -1}};
if (a <= l && r <= b) {
if (lcait.node[i] == v) return {lcait.node[i], {l, r}};
}
if (l == r) return {lcait.node[i], {l, r}};
int mid = l + r >> 1;
pair <int, pair <int, int> > lef = solve(i << 1, l, mid, a, b, v);
pair <int, pair <int, int> > rig = solve(i << 1 | 1, mid + 1, r, a, b, v);
if (lef.first == v) return lef;
if (rig.first == v) return rig;
int maxlef = prone_max_left(1, 1, m, l, mid, en[v]);
int minlef = prone_min_left(1, 1, m, l, mid, st[v]);
int maxrig = prone_max_right(1, 1, m, mid + 1, r, en[v]);
int minrig = prone_min_right(1, 1, m, mid + 1, r, st[v]);
int lefpos = max(maxlef, minlef);
int rigpos = min(maxrig, minrig);
lefpos = max(lefpos, a);
rigpos = min(rigpos, b);
int get_lca = lcait.query(1, 1, m, lefpos, rigpos);
return {get_lca, {lefpos, rigpos}};
}
} proneit;
int main(){
scanf("%d %d %d", &n, &m, &q); memset(par, -1, sizeof(par));
for (int i = 1; i <= n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
dfs(1, 1);
makeLCA();
lcait.init(1, 1, m);
proneit.init(1, 1, m);
while (q--) {
int type;
scanf("%d", &type);
if (type == 1) {
int pos, v;
scanf("%d %d", &pos, &v);
lcait.update(1, 1, m, pos, v);
proneit.update(1, 1, m, pos, v);
}
else {
int l, r, v;
scanf("%d %d %d", &l, &r, &v);
pair <int, pair <int, int> > ans = proneit.solve(1, 1, m, l, r, v);
if (ans.first == v) printf("%d %d\n", ans.second.first, ans.second.second);
else printf("%d %d\n", -1, -1);
}
}
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
5 4 1
1 2
3 1
3 4
5 3
2 4 5 1
2 1 4 3
*/
Compilation message
treearray.cpp: In member function 'void LCAIT::init(int, int, int)':
treearray.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
treearray.cpp: In member function 'void LCAIT::update(int, int, int, int, int)':
treearray.cpp:67:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
treearray.cpp: In member function 'int LCAIT::query(int, int, int, int, int)':
treearray.cpp:77:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
treearray.cpp: In member function 'void ProneIT::init(int, int, int)':
treearray.cpp:97:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
treearray.cpp: In member function 'void ProneIT::update(int, int, int, int, int)':
treearray.cpp:109:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
treearray.cpp: In member function 'ProneIT::Node ProneIT::query(int, int, int, int, int)':
treearray.cpp:119:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
treearray.cpp: In member function 'int ProneIT::prone_max_left(int, int, int, int, int, int)':
treearray.cpp:134:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
treearray.cpp: In member function 'int ProneIT::prone_min_left(int, int, int, int, int, int)':
treearray.cpp:151:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
treearray.cpp: In member function 'int ProneIT::prone_max_right(int, int, int, int, int, int)':
treearray.cpp:168:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
treearray.cpp: In member function 'int ProneIT::prone_min_right(int, int, int, int, int, int)':
treearray.cpp:185:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
treearray.cpp: In member function 'std::pair<int, std::pair<int, int> > ProneIT::solve(int, int, int, int, int, int)':
treearray.cpp:199:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
treearray.cpp: In function 'int main()':
treearray.cpp:219:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &q); memset(par, -1, sizeof(par));
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:222:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:227:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
treearray.cpp:235:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &type);
~~~~~^~~~~~~~~~~~~
treearray.cpp:238:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &pos, &v);
~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:244:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &l, &r, &v);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
27008 KB |
n=5 |
| 2 |
Incorrect |
23 ms |
27000 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
27008 KB |
n=5 |
| 2 |
Incorrect |
23 ms |
27000 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
27008 KB |
n=5 |
| 2 |
Incorrect |
23 ms |
27000 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
27008 KB |
n=5 |
| 2 |
Incorrect |
23 ms |
27000 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
