# Submit Info #3003

Problem Lang User Status Time Memory
Lowest Common Ancestor cpp cookies RE 228 ms 78.51 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.63 MiB
line_00 RE 209 ms 66.25 MiB
line_01 RE 227 ms 78.51 MiB
line_02 RE 110 ms 8.39 MiB
line_03 RE 217 ms 72.88 MiB
line_04 RE 176 ms 47.30 MiB
random_00 RE 204 ms 66.25 MiB
random_01 RE 228 ms 78.51 MiB
random_02 RE 109 ms 8.38 MiB
random_03 RE 218 ms 72.85 MiB
random_04 RE 172 ms 47.26 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); } d=1; while(1L<<d < n) 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); for(long i=d-1; i>=0; i--) if(h[v]-h[u] >= 1L<<i) v = park[i][v]; if(v == u) return v; for(long i=d-1; i>=0; i--) if(park[i][v] != park[i][u]) v = park[i][v], 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; } }