Submit Info #3008

Problem Lang User Status Time Memory
Lowest Common Ancestor cpp cookies AC 1189 ms 78.50 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.62 MiB
line_00 AC 1139 ms 66.17 MiB
line_01 AC 1189 ms 78.50 MiB
line_02 AC 708 ms 10.14 MiB
line_03 AC 205 ms 72.78 MiB
line_04 AC 324 ms 47.30 MiB
random_00 AC 963 ms 66.17 MiB
random_01 AC 989 ms 78.49 MiB
random_02 AC 660 ms 8.76 MiB
random_03 AC 191 ms 72.88 MiB
random_04 AC 285 ms 47.25 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++) { if(park[k-1][i] == -1) continue; 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, -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; } }