# Submit Info #2999

Problem Lang User Status Time Memory
Lowest Common Ancestor cpp cookies RE 230 ms 82.09 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.66 MiB
line_00 RE 208 ms 69.14 MiB
line_01 RE 230 ms 82.01 MiB
line_02 RE 108 ms 8.80 MiB
line_03 RE 220 ms 76.08 MiB
line_04 RE 177 ms 49.43 MiB
random_00 RE 207 ms 69.12 MiB
random_01 RE 228 ms 82.09 MiB
random_02 RE 110 ms 8.77 MiB
random_03 RE 218 ms 76.14 MiB
random_04 RE 172 ms 49.38 MiB

#include<bits/stdc++.h> using namespace std; struct LCA { vector<vector<long>> park; vector<long> h; long n, d; LCA(vector<long> &par) { // par[root] == -1 n = par.size(); h.assign(n, -1); { auto dfs = [&](auto dfs, long cur) -> long { if(par[cur] == -1) return h[cur] = 0; if(h[cur] != -1) return h[cur]; return h[cur] = 1 + dfs(dfs, par[cur]); }; for(long i=0; i<n; i++) dfs(dfs, i); } for(d=0; 1L<<d < n; d++); d++; park.assign(d, vector<long>(n)); copy(par.begin(), par.end(), park[0].begin()); for(long k=1; k<d; k++) for(long i=0; i<n; i++) park[k][i] = park[k-1][park[k-1][i]]; } long query(long u, long v) const { if(h[u] > h[v]) swap(u, v); assert(h[u] <= h[v]); for(long i=d-1; i>=0; i--) if(h[v]-h[u] >= 1L<<i) v = park[i][v]; assert(h[v] == h[u]); if(v == u) return v; for(long i=d-1; i>=0; i--) if(park[i][v] != park[i][u]) v = park[i][u], u = park[i][u]; return park[0][v]; } }; int main(void) { long n, q; cin >> n >> q; vector<long> par(n); par[0] = -1; for(int i=1; i<n; i++) cin >> par[i]; LCA lca(par); for(long i=0; i<q; i++) { long u, v; cin >> u >> v; cout << lca.query(u, v) << endl; } }