This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#define PROBLEM "https://judge.yosupo.jp/problem/lca" #include <bits/stdc++.h> using namespace std; #include "tree/lca.hpp" signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); 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), g[i].push_back(p); } auto lca_tree = lca(g, 0); while (q--) { int u, v; cin >> u >> v; cout << lca_tree.get(u, v) << '\n'; } }
#line 1 "tree/test/Lowest_Common_Ancestor.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/lca" #include <bits/stdc++.h> using namespace std; #line 2 "tree/lca.hpp" struct lca { int n, l; vector<int> in, out, depth; vector<vector<int>> up; lca(const vector<vector<int>> &g, int root) : n(g.size()), l(__lg(n) + 1), in(n), out(n), depth(n), up(n, vector<int>(l)) { int timer = 0; auto dfs = [&](auto dfs, int p, int u, int d = 0) -> void { in[u] = timer++; up[u][0] = p; depth[u] = d; for (int i = 1; i < l; ++i) { up[u][i] = up[up[u][i - 1]][i - 1]; } for (auto v : g[u]) if (v != p) dfs(dfs, u, v, d + 1); out[u] = timer++; }; dfs(dfs, root, root); }; bool is_anc(int u, int v) const { return in[u] <= in[v] && out[u] >= out[v]; } int dist(int u, int v) const { return depth[u] + depth[v] - 2 * depth[get(u, v)]; } int get(int u, int v) const { if (is_anc(u, v)) return u; if (is_anc(v, u)) return v; for (int i = l - 1; i >= 0; --i) { if (!is_anc(up[u][i], v)) u = up[u][i]; } return up[u][0]; } }; #line 8 "tree/test/Lowest_Common_Ancestor.test.cpp" signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); 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), g[i].push_back(p); } auto lca_tree = lca(g, 0); while (q--) { int u, v; cin >> u >> v; cout << lca_tree.get(u, v) << '\n'; } }