#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N = 2e5+5;
int n, m, q;
vector<int> adj[N];
int a[N];
int cnt = 0;
int be[N], en[N], h[N], par[N];
pair<int, int> b[N*2];
pair<int, int> rmq[20][N*2];
struct LCANode {
int all, left, right, lpos, rpos;
int be, en;
};
LCANode it[N*4], res[N*4];
int ans_x, ans_y;
void dfs(int u) {
b[++cnt] = mp(h[u], u);
be[u] = en[u] = cnt;
for (int &v: adj[u]) if (v != par[u]) {
par[v] = u;
h[v] = h[u] + 1;
dfs(v);
b[++cnt] = mp(h[u], u);
en[u] = cnt;
}
}
void build_rmq() {
for (int i = 1; i <= cnt; ++i) {
rmq[0][i] = b[i];
}
for (int j = 1; (1 << j) <= cnt; ++j) {
for (int i = 1; i + (1 << j) <= cnt; ++i) {
rmq[j][i] = min(rmq[j-1][i], rmq[j-1][i + (1 << j-1)]);
}
}
}
int get_lca(int &u, int &v) {
int l = be[u], r = be[v];
if (l > r) swap(l, r);
int k = log2(r-l+1);
auto mi = min(rmq[k][l], rmq[k][r - (1<<k) +1]);
return mi.second;
}
void build(int k, int l, int r) {
if (l == r) {
it[k].all = a[r];
it[k].be = be[a[r]];
it[k].en = en[a[r]];
return;
}
int m = (l + r) >> 1;
build(k*2, l, m);
build(k*2+1, m+1, r);
it[k].all = get_lca(it[k*2].all, it[k*2+1].all);
it[k].be = min(it[k*2].be, it[k*2+1].be);
it[k].en = max(it[k*2].en, it[k*2+1].en);
}
void update(int k, int l, int r, int &i, int &u, int &old_u) {
if (l == r) {
it[k].all = u;
it[k].be = be[u];
it[k].en = en[u];
return;
}
int m = (l + r) >> 1;
if (i <= m) update(k*2, l, m, i, u, old_u);
else update(k*2+1, m+1, r, i, u, old_u);
it[k].all = get_lca(it[k*2].all, it[k*2+1].all);
it[k].be = min(it[k*2].be, it[k*2+1].be);
it[k].en = max(it[k*2].en, it[k*2+1].en);
}
void merge_node(LCANode &node, LCANode &lnode, LCANode &rnode, int u) {
if (lnode.all && rnode.all) {
int lca = get_lca(lnode.all, rnode.all);
node.all = node.left = node.right = lca;
node.lpos = rnode.lpos;
node.rpos = lnode.rpos;
return;
}
node.all = 0;
node.left = lnode.left;
node.right = rnode.right;
node.lpos = lnode.lpos;
node.rpos = rnode.rpos;
if (lnode.all && rnode.left) {
node.left = get_lca(lnode.all, rnode.left);
node.lpos = rnode.lpos;
}
if (rnode.all && lnode.right) {
node.right = get_lca(rnode.all, lnode.right);
node.rpos = lnode.rpos;
}
if (lnode.right && rnode.left) {
int lca = get_lca(lnode.right, rnode.left);
if (lca == u) {
ans_x = lnode.rpos;
ans_y = rnode.lpos;
}
}
}
void get(int k, int l, int r, int &ql, int &qr, int &u) {
if (qr < l || r < ql || it[k].en < be[u] || en[u] < it[k].be) {
// res[k] = LCANode{0, 0, 0, l-1, r+1};
res[k].all = 0;
res[k].left = 0;
res[k].right = 0;
res[k].lpos = l-1;
res[k].rpos = r+1;
return;
}
if (ql <= l && r <= qr && get_lca(it[k].all, u) == u) {
// cout << "a " << l << ' ' << r << ' ' << it[k].all << endl;
int lca = it[k].all;
if (lca == u) {
ans_x = l;
ans_y = r;
}
// res[k] = LCANode{lca, lca, lca, r, l};
res[k].all = res[k].left = res[k].right = lca;
res[k].lpos = r;
res[k].rpos = l;
return;
}
assert(l < r);
int m = (l + r) >> 1;
get(k*2, l, m, ql, qr, u);
if (ans_x) return;
get(k*2+1, m+1, r, ql, qr, u);
if (ans_x) return;
merge_node(res[k], res[k*2], res[k*2+1], u);
// cout << l << ' ' << r << ' ' << node.all << ' ' << node.left << ' ' << node.right << endl;
// cout << lnode.all << ' ' << lnode.left << ' ' << lnode.right << endl;
// cout << rnode.all << ' ' << rnode.left << ' ' << rnode.right << endl;
}
int main()
{
// freopen("a.inp", "r", stdin);
cin >> n >> m >> q;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= m; ++i) {
cin >> a[i];
}
dfs(1);
build_rmq();
// for (int i = 1; i <= cnt; ++i) cout << b[i].second << ' ';
// cout << endl;
// cout << "lca " << get_lca(4, 5) << endl;
build(1, 1, m);
for (int i = 1; i <= q; ++i) {
int t;
cin >> t;
if (t == 1) {
int pos, u;
cin >> pos >> u;
update(1, 1, m, pos, u, a[pos]);
a[pos] = u;
} else {
int l, r, u;
cin >> l >> r >> u;
ans_x = ans_y = 0;
get(1, 1, m, l, r, u);
if (ans_x) cout << ans_x << ' ' << ans_y << '\n';
else cout << -1 << ' ' << -1 << '\n';
}
}
return 0;
}
Compilation message
treearray.cpp: In function 'void build_rmq()':
treearray.cpp:46:62: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
46 | rmq[j][i] = min(rmq[j-1][i], rmq[j-1][i + (1 << j-1)]);
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
19804 KB |
n=5 |
| 2 |
Runtime error |
26 ms |
56668 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
19804 KB |
n=5 |
| 2 |
Runtime error |
26 ms |
56668 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
19804 KB |
n=5 |
| 2 |
Runtime error |
26 ms |
56668 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
19804 KB |
n=5 |
| 2 |
Runtime error |
26 ms |
56668 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
