#include <bits/stdc++.h>
using namespace std;
const int LOG = 20;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
vector<int> a(m);
for (int i = 0; i < m; i++) {
cin >> a[i];
a[i]--;
}
vector<int> dep(n);
vector<vector<int>> anc(LOG, vector<int>(n, -1));
function<void(int, int)> dfs = [&](int u, int p) {
anc[0][u] = p;
for (int i = 1; i < LOG; i++) {
if (anc[i - 1][u] != -1) {
anc[i][u] = anc[i - 1][anc[i - 1][u]];
}
}
for (int v : adj[u]) {
if (v != p) {
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
};
dfs(0, -1);
function<int(int, int)> lca = [&](int u, int v) {
if (dep[u] < dep[v]) {
swap(u, v);
}
int x = dep[u] - dep[v];
for (int i = LOG - 1; i >= 0; i--) {
if (x & (1 << i)) {
u = anc[i][u];
}
}
if (u == v) {
return u;
}
for (int i = LOG - 1; i >= 0; i--) {
if (anc[i][u] != anc[i][v]) {
u = anc[i][u];
v = anc[i][v];
}
}
return anc[0][u];
};
vector<set<int>> s(n), s1(n);
for (int i = 0; i < m; i++) {
if (i < m - 1) {
s[lca(a[i], a[i + 1])].insert(i);
}
s1[a[i]].insert(i);
}
while (q--) {
int op;
cin >> op;
if (op == 1) {
int pos, v;
cin >> pos >> v;
pos--;
v--;
s1[a[pos]].erase(pos);
s1[v].insert(pos);
if (pos < m - 1) {
s[lca(a[pos], a[pos + 1])].erase(pos);
s[lca(v, a[pos + 1])].insert(pos);
}
if (pos > 0) {
s[lca(a[pos - 1], a[pos])].erase(pos - 1);
s[lca(a[pos - 1], v)].insert(pos - 1);
}
a[pos] = v;
} else {
int l, r, k;
cin >> l >> r >> k;
l--;
r--;
k--;
set<int>::iterator it = s[k].lower_bound(l);
if (it != s[k].end() && *it < r) {
cout << *it << ' ' << *it + 1 << '\n';
continue;
}
it = s1[k].lower_bound(l);
if (it != s1[k].end() && *it <= r) {
cout << *it << ' ' << *it << '\n';
continue;
}
cout << -1 << ' ' << -1 << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Wrong range. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Wrong range. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Wrong range. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Wrong range. |
| 2 |
Halted |
0 ms |
0 KB |
- |
