This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "https://judge.yosupo.jp/problem/lca" #include <bits/stdc++.h> using namespace std; #include "../LCA.h" #include "../../buffered_reader.h" #define FOR(i, a, b) for (int i = (a), _##i = (b); i <= _##i; ++i) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n = IO::get<int>(); int q = IO::get<int>(); vector<vector<int>> adj(n); FOR(i,1,n-1) { int pi = IO::get<int>(); adj[i].push_back(pi); adj[pi].push_back(i); } LCA lca(n, adj, 0); while (q--) { int u = IO::get<int>(); int v = IO::get<int>(); cout << lca.lca(u, v) << '\n'; } return 0; }
#line 1 "DataStructure/test/lca.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/lca" #include <bits/stdc++.h> using namespace std; #line 1 "DataStructure/LCA.h" // LCA // Notes: // - Index from 0 // - Cannot use for queries like min edge in path u -> v // // Tested: // - https://judge.yosupo.jp/problem/lca #line 1 "DataStructure/RMQ.h" // RMQ {{{ // // Sparse table // Usage: // RMQ<int, _min> st(v); // // Note: // - doesn't work for empty range // // Tested: // - https://judge.yosupo.jp/problem/staticrmq template<class T, T (*op) (T, T)> struct RMQ { RMQ() = default; RMQ(const vector<T>& v) : t{v}, n{(int) v.size()} { for (int k = 1; (1<<k) <= n; ++k) { t.emplace_back(n - (1<<k) + 1); for (int i = 0; i + (1<<k) <= n; ++i) { t[k][i] = op(t[k-1][i], t[k-1][i + (1<<(k-1))]); } } } // get range [l, r-1] // doesn't work for empty range T get(int l, int r) const { assert(0 <= l && l < r && r <= n); int k = __lg(r - l); return op(t[k][l], t[k][r - (1<<k)]); } private: vector<vector<T>> t; int n; }; template<class T> T _min(T a, T b) { return b < a ? b : a; } template<class T> T _max(T a, T b) { return a < b ? b : a; } // }}} #line 9 "DataStructure/LCA.h" struct LCA { const int n; vector<vector<int>> adj; const int root; using P = pair<int,int>; static P f(P x, P y) { return std::min(x, y); } LCA(int _n, const vector<vector<int>>& _adj, int _root) : n(_n), adj(_adj), root(_root) { assert(0 <= root && root < n); id.resize(n); depth.resize(n); order.reserve(2 * n); dfs(root, -1, 0); rmq = RMQ<P, f>(order); } int lca(int u, int v) { assert(0 <= u && u < n); assert(0 <= v && v < n); int x = id[u], y = id[v]; if (x > y) std::swap(x, y); return rmq.get(x, y+1).second; } // private: vector<int> id, depth; vector<P> order; RMQ<P, f> rmq; void dfs(int u, int fu, int d) { id[u] = order.size(); depth[u] = d; order.emplace_back(d, u); for (int v : adj[u]) { if (v == fu) continue; dfs(v, u, d + 1); order.emplace_back(d, u); } } }; #line 1 "buffered_reader.h" // Buffered reader {{{ namespace IO { const int BUFSIZE = 1<<14; char buf[BUFSIZE + 1], *inp = buf; bool reacheof; char get_char() { if (!*inp && !reacheof) { memset(buf, 0, sizeof buf); int tmp = fread(buf, 1, BUFSIZE, stdin); if (tmp != BUFSIZE) reacheof = true; inp = buf; } return *inp++; } template<typename T> T get() { int neg = 0; T res = 0; char c = get_char(); while (!std::isdigit(c) && c != '-' && c != '+') c = get_char(); if (c == '+') { neg = 0; } else if (c == '-') { neg = 1; } else res = c - '0'; c = get_char(); while (std::isdigit(c)) { res = res * 10 + (c - '0'); c = get_char(); } return neg ? -res : res; } }; // Helper methods int ri() { return IO::get<int>(); } // }}} #line 8 "DataStructure/test/lca.test.cpp" #define FOR(i, a, b) for (int i = (a), _##i = (b); i <= _##i; ++i) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n = IO::get<int>(); int q = IO::get<int>(); vector<vector<int>> adj(n); FOR(i,1,n-1) { int pi = IO::get<int>(); adj[i].push_back(pi); adj[pi].push_back(i); } LCA lca(n, adj, 0); while (q--) { int u = IO::get<int>(); int v = IO::get<int>(); cout << lca.lca(u, v) << '\n'; } return 0; }