Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3645

Problem Lang User Status Time Memory
Lowest Common Ancestor cpp satashun AC 529 ms 77.10 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.63 MiB
line_00 AC 524 ms 65.36 MiB
line_01 AC 529 ms 77.10 MiB
line_02 AC 159 ms 10.67 MiB
line_03 AC 126 ms 69.15 MiB
line_04 AC 158 ms 45.32 MiB
random_00 AC 475 ms 47.85 MiB
random_01 AC 506 ms 56.65 MiB
random_02 AC 150 ms 7.17 MiB
random_03 AC 207 ms 51.82 MiB
random_04 AC 182 ms 33.88 MiB

#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; typedef long long ll; template<class T> using V = vector<T>; template<class T> using VV = V<V<T>>; #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define rep(i,n) rep2(i,0,n) #define rep2(i,m,n) for(int i=m;i<(n);i++) #define ALL(c) (c).begin(),(c).end() #ifdef LOCAL #define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl #else #define dump(x) true #endif constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); } template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; } template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; } template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os<<"("<<p.first<<","<<p.second<<")"; return os; } template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { os<<"{"; rep(i, v.size()) { if (i) os<<","; os<<v[i]; } os<<"}"; return os; } //E : int or edge class template<class E> struct LCA { VV<int> anc; V<int> dep; int lg; const VV<E>& g; LCA(const VV<E>& g, int root) : g(g) { int n = g.size(); lg = 1; while ((1 << lg) < n) lg++; anc = VV<int>(lg, V<int>(n, -1)); dep = V<int>(n); dfs(root, -1, 0); for (int i = 1; i < lg; i++) { for (int j = 0; j < n; j++) { anc[i][j] = (anc[i - 1][j] == -1) ? -1 : anc[i - 1][anc[i - 1][j]]; } } } void dfs(int v, int p, int d) { anc[0][v] = p; dep[v] = d; for (auto e : g[v]) { int to = e; if (to == p) continue; dfs(to, v, d + 1); } } int query(int u, int v) { if (dep[u] < dep[v]) swap(u, v); int df = dep[u] - dep[v]; for (int i = lg - 1; i >= 0; --i) { if ((df >> i) & 1) { df -= (1 << i); u = anc[i][u]; } } if (u == v) return u; for (int i = lg - 1; i >= 0; --i) { if (anc[i][u] != anc[i][v]) { u = anc[i][u]; v = anc[i][v]; } } return anc[0][u]; } }; int main() { int N, Q; scanf("%d %d", &N, &Q); V<int> p(N); VV<int> g(N); for (int i = 1; i < N; ++i) { scanf("%d", &p[i]); g[p[i]].pb(i); } LCA<int> lca(g, 0); while (Q--) { int a, b; scanf("%d %d", &a, &b); int v = lca.query(a, b); printf("%d\n", v); } return 0; }