#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cassert>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cassert>
using namespace std;
vector<int>depth;
vector<vector<int>>edges;
vector<vector<int>>anc;
vector<int>inorder;
vector<int>preorder;
void dfs(int root, int dep) {
depth[root] = dep;
for (auto i : edges[root]) {
if (anc[root][0] != i) {
anc[i][0] = root;
dfs(i, dep + 1);
}
}
}
void init(int n) {
depth.resize(n + 1, 0);
edges.resize(n + 1);
anc.resize(n + 1, vector<int>(18));
inorder.resize(n + 1);
preorder.resize(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
edges[u].push_back(v);
edges[v].push_back(u);
}
dfs(1, 1);
for (int i = 1; i < 18; i++) {
for (int j = 1; j <= n; j++) {
anc[j][i] = anc[anc[j][i - 1]][i - 1];
}
}
}
int lca(int u, int v) {
if (depth[u] < depth[v])swap(u, v);
int k = depth[u] - depth[v];
for (int i = 0; k; i++) {
if (k & 1)u = anc[u][i];
k >>= 1;
}
for (int i = 17; i >= 0; i--) {
if (anc[u][i] != anc[v][i]) {
u = anc[u][i];
v = anc[v][i];
}
}
if (u == v)return u;
return anc[u][0];
}
vector<int>seq;
pair<int, int>dc(int l, int r, int v) {
if (l == r) {
if (seq[l] == v)return make_pair(l, l);
else return make_pair(-1, -1);
}
int m = (l + r) >> 1;
pair<int, int>lans = dc(l, m, v), rans = dc(m + 1, r, v);
if (lans.first != -1)return lans;
if (rans.first != -1)return rans;
set<int>cofv;
vector<int>ret;
for (int lm = m, llca = seq[m]; lm >= l; lm--) {
llca = lca(llca, seq[lm]);
if (depth[llca] < depth[v])break;
int step = depth[llca] - depth[v] - 1;
int temp = llca;
assert(step >= 0);
for (int i = 0; step; i++) {
if (step & 1)temp = anc[temp][i];
step >>= 1;
}
if (!cofv.count(temp)) {
cofv.insert(temp);
ret.push_back(lm);
break;
}
}
for (int rm = m+1, rlca = seq[m+1]; rm <= r; rm++) {
rlca = lca(rlca, seq[rm]);
if (depth[rlca] < depth[v])break;
int step = depth[rlca] - depth[v] - 1;
int temp = rlca;
assert(step >= 0);
for (int i = 0; step; i++) {
if (step & 1)temp = anc[temp][i];
step >>= 1;
}
if (!cofv.count(temp)) {
cofv.insert(temp);
ret.push_back(rm);
break;
}
}
assert(cofv.size() <= 2);
if (cofv.size() == 2) {
return make_pair(ret[0], ret[1]);
}
return make_pair(-1, -1);
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
init(n);
seq.resize(m + 1);
for (int i = 1; i <= m; i++) {
cin >> seq[i];
}
for (int i = 0; i < q; i++) {
int c;
cin >> c;
if (c == 1) {
int pos, v;
cin >> pos >> v;
seq[pos] = v;
}
else {
int l, r, v;
cin >> l >> r >> v;
pair<int, int>ans = dc(l, r, v);
cout << ans.first << ' ' << ans.second << endl;
}
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
n=5 |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
n=5 |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
n=5 |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
n=5 |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
