This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/lca
#include "../LCA.cpp"
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
int p;
cin >> p;
g[p].push_back(i);
}
lca_tree lt(g);
while (q--) {
int u, v;
cin >> u >> v;
cout << lt.lca(u, v) << "\n";
}
}
#line 1 "test/LCA.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/lca
#line 1 "LCA.cpp"
#include <bits/stdc++.h>
#line 2 "SparseTable.cpp"
using namespace std;
template <class T, T (*op)(T, T), T (*e)()>
struct sparsetable {
vector<vector<T>> table;
vector<int> logtable;
sparsetable() = default;
sparsetable(vector<T> v) {
int len = 0;
while ((1 << len) <= (int)v.size()) len++;
table.assign(len, vector<T>(1 << len));
for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
for (int i = 1; i < len; i++) {
for (int j = 0; j + (1 << i) <= (1 << len); j++) {
table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
}
logtable.resize((int)v.size() + 1);
for (int i = 2; i < (int)logtable.size(); i++) {
logtable[i] = logtable[(i >> 1)] + 1;
}
}
T query(int l, int r) {
assert(l <= r);
if (l == r) return e();
int len = logtable[r - l];
return op(table[len][l], table[len][r - (1 << len)]);
}
};
template <class T, T (*op)(T, T), T (*e)()>
struct disjointsparsetable {
vector<vector<T>> table;
vector<int> logtable;
disjointsparsetable() = default;
disjointsparsetable(vector<T> v) {
int len = 0;
while ((1 << len) <= v.size()) len++;
table.assign(len, vector<T>(1 << len, e()));
for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
for (int i = 1; i < len; i++) {
int shift = 1 << i;
for (int j = 0; j < (int)v.size(); j += shift << 1) {
int t = min(j + shift, (int)v.size());
table[i][t - 1] = v[t - 1];
for (int k = t - 2; k >= j; k--) table[i][k] = op(v[k], table[i][k + 1]);
if (v.size() <= t) break;
table[i][t] = v[t];
int r = min(t + shift, (int)v.size());
for (int k = t + 1; k < r; k++) table[i][k] = op(table[i][k - 1], v[k]);
}
}
logtable.resize(1 << len);
for (int i = 2; i < logtable.size(); i++) {
logtable[i] = logtable[(i >> 1)] + 1;
}
}
T query(int l, int r) {
if (l == r) return e();
if (l >= --r) return table[0][l];
int len = logtable[l ^ r];
return op(table[len][l], table[len][r]);
};
};
#line 3 "LCA.cpp"
using namespace std;
pair<int, int> lcatree_op(pair<int, int> a, pair<int, int> b) { return min(a, b); }
pair<int, int> lcatree_e() { return {1000000000, -1}; }
struct lca_tree {
int n, size;
vector<int> in, ord, depth;
disjointsparsetable<pair<int, int>, lcatree_op, lcatree_e> st;
lca_tree(vector<vector<int>> g, int root = 0) : n((int)g.size()), size(log2(n) + 2), in(n), depth(n, n) {
depth[root] = 0;
function<void(int, int)> dfs = [&](int v, int p) {
in[v] = (int)ord.size();
ord.push_back(v);
for (int u : g[v]) {
if (u == p) continue;
if (depth[u] > depth[v] + 1) {
depth[u] = depth[v] + 1;
dfs(u, v);
ord.push_back(v);
}
}
};
dfs(root, -1);
vector<pair<int, int>> vec((int)ord.size());
for (int i = 0; i < (int)ord.size(); i++) {
vec[i] = make_pair(depth[ord[i]], ord[i]);
}
st = vec;
}
int lca(int u, int v) {
if (in[u] > in[v]) swap(u, v);
if (u == v) return u;
return st.query(in[u], in[v]).second;
}
int dist(int u, int v) {
int l = lca(u, v);
return depth[u] + depth[v] - 2 * depth[l];
}
};
#line 3 "test/LCA.test.cpp"
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
int p;
cin >> p;
g[p].push_back(i);
}
lca_tree lt(g);
while (q--) {
int u, v;
cin >> u >> v;
cout << lt.lca(u, v) << "\n";
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | almost_line_00 |
![]() |
449 ms | 269 MB |
g++ | almost_line_01 |
![]() |
434 ms | 269 MB |
g++ | binary_00 |
![]() |
448 ms | 238 MB |
g++ | binary_01 |
![]() |
465 ms | 238 MB |
g++ | binary_02 |
![]() |
477 ms | 238 MB |
g++ | example_00 |
![]() |
5 ms | 4 MB |
g++ | line_00 |
![]() |
347 ms | 279 MB |
g++ | line_01 |
![]() |
383 ms | 299 MB |
g++ | line_02 |
![]() |
114 ms | 36 MB |
g++ | line_03 |
![]() |
262 ms | 290 MB |
g++ | line_04 |
![]() |
206 ms | 250 MB |
g++ | max_line_00 |
![]() |
407 ms | 308 MB |
g++ | max_line_01 |
![]() |
431 ms | 308 MB |
g++ | max_line_02 |
![]() |
446 ms | 308 MB |
g++ | max_random_00 |
![]() |
459 ms | 238 MB |
g++ | max_random_01 |
![]() |
473 ms | 238 MB |
g++ | max_random_02 |
![]() |
474 ms | 238 MB |
g++ | path_graph_root_centroid_00 |
![]() |
371 ms | 281 MB |
g++ | path_graph_root_centroid_01 |
![]() |
373 ms | 281 MB |
g++ | path_graph_root_centroid_02 |
![]() |
374 ms | 281 MB |
g++ | random_00 |
![]() |
387 ms | 225 MB |
g++ | random_01 |
![]() |
440 ms | 234 MB |
g++ | random_02 |
![]() |
118 ms | 29 MB |
g++ | random_03 |
![]() |
298 ms | 230 MB |
g++ | random_04 |
![]() |
208 ms | 212 MB |
clang++ | almost_line_00 |
![]() |
425 ms | 266 MB |
clang++ | almost_line_01 |
![]() |
420 ms | 265 MB |
clang++ | binary_00 |
![]() |
470 ms | 238 MB |
clang++ | binary_01 |
![]() |
460 ms | 238 MB |
clang++ | binary_02 |
![]() |
448 ms | 238 MB |
clang++ | example_00 |
![]() |
5 ms | 4 MB |
clang++ | line_00 |
![]() |
334 ms | 273 MB |
clang++ | line_01 |
![]() |
369 ms | 291 MB |
clang++ | line_02 |
![]() |
112 ms | 35 MB |
clang++ | line_03 |
![]() |
249 ms | 284 MB |
clang++ | line_04 |
![]() |
197 ms | 246 MB |
clang++ | max_line_00 |
![]() |
402 ms | 301 MB |
clang++ | max_line_01 |
![]() |
393 ms | 301 MB |
clang++ | max_line_02 |
![]() |
409 ms | 301 MB |
clang++ | max_random_00 |
![]() |
482 ms | 238 MB |
clang++ | max_random_01 |
![]() |
471 ms | 238 MB |
clang++ | max_random_02 |
![]() |
462 ms | 238 MB |
clang++ | path_graph_root_centroid_00 |
![]() |
356 ms | 277 MB |
clang++ | path_graph_root_centroid_01 |
![]() |
360 ms | 277 MB |
clang++ | path_graph_root_centroid_02 |
![]() |
365 ms | 277 MB |
clang++ | random_00 |
![]() |
361 ms | 225 MB |
clang++ | random_01 |
![]() |
400 ms | 234 MB |
clang++ | random_02 |
![]() |
114 ms | 29 MB |
clang++ | random_03 |
![]() |
271 ms | 230 MB |
clang++ | random_04 |
![]() |
203 ms | 211 MB |