This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ruthen71/rcpl
#define PROBLEM "https://judge.yosupo.jp/problem/lca" #include <bits/stdc++.h> #include "graph/lowest_common_ancestor.hpp" int main() { int N, Q; std::cin >> N >> Q; Graph<int> G(N); for (int i = 1; i < N; i++) { int p; std::cin >> p; G[i].push_back(Edge(i, p, 1, i - 1)); G[p].push_back(Edge(p, i, 1, i - 1)); } LowestCommonAncestor tq(G, 0); while (Q--) { int u, v; std::cin >> u >> v; std::cout << tq.lca(u, v) << '\n'; } return 0; }
#line 1 "verify/lc_tree/lc_lowest_common_ancestor.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/lca" #include <bits/stdc++.h> #line 2 "graph/lowest_common_ancestor.hpp" #line 2 "graph/graph_template.hpp" #line 4 "graph/graph_template.hpp" template <class T> struct Edge { int from, to; T cost; int id; Edge() = default; Edge(int from, int to, T cost = 1, int id = -1) : from(from), to(to), cost(cost), id(id) {} friend std::ostream &operator<<(std::ostream &os, const Edge<T> &e) { // output format: "{ id : from -> to, cost }" return os << "{ " << e.id << " : " << e.from << " -> " << e.to << ", " << e.cost << " }"; } }; template <class T> using Edges = std::vector<Edge<T>>; template <class T> using Graph = std::vector<std::vector<Edge<T>>>; #line 4 "graph/lowest_common_ancestor.hpp" template <class T> struct LowestCommonAncestor { std::vector<int> depth; std::vector<std::vector<int>> parent; int n, LOG; LowestCommonAncestor(const Graph<T> &G, int root = 0) : n(int(G.size())), LOG(32 - __builtin_clz(n)) { depth.assign(n, 0); parent.assign(LOG, std::vector<int>(n)); auto dfs = [&](auto f, int cur, int par) -> void { parent[0][cur] = par; for (auto &e : G[cur]) { if (e.to == par) continue; depth[e.to] = depth[cur] + 1; f(f, e.to, cur); } }; dfs(dfs, root, -1); for (int k = 0; k + 1 < LOG; k++) { for (int v = 0; v < n; v++) { parent[k + 1][v] = (parent[k][v] < 0 ? -1 : parent[k][parent[k][v]]); } } } int lca(int u, int v) { assert((int)depth.size() == n); if (depth[u] > depth[v]) std::swap(u, v); // depth[u] <= depth[v] for (int k = 0; k < LOG; k++) if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v]; if (u == v) return u; for (int k = LOG - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int level_ancestor(int u, int d) { assert((int)depth.size() == n); if (depth[u] < d) return -1; for (int k = 0; k < LOG; k++) if (d >> k & 1) u = parent[k][u]; return u; } int distance(int u, int v) { int par = lca(u, v); return depth[u] + depth[v] - 2 * depth[par]; } }; #line 6 "verify/lc_tree/lc_lowest_common_ancestor.test.cpp" int main() { int N, Q; std::cin >> N >> Q; Graph<int> G(N); for (int i = 1; i < N; i++) { int p; std::cin >> p; G[i].push_back(Edge(i, p, 1, i - 1)); G[p].push_back(Edge(p, i, 1, i - 1)); } LowestCommonAncestor tq(G, 0); while (Q--) { int u, v; std::cin >> u >> v; std::cout << tq.lca(u, v) << '\n'; } return 0; }