

Revision History 

In the article's "Another easy solution in <o logn o>" of LCA, it uses dynamic programming, with the following recursion:
When j = 0, then: P[i] [j] = T[i]; When j > 0, then: P[i] [j] = P[ P[i] [j1] ] [j1]
Since P[i] [j] is the (2^j)th ancestor of i, when j > 0, I think P[i][j] should be:
P[i] [j] = P[ P[i] [j1] ] [1]
Please correct me if I am wrong. Thank you.</o>
Updated on 10/06/2015: Never mind, the original version is correct.


In the article's "Another easy solution in <O(N logN, O(logN)>" of LCA, it uses dynamic programming, with the following recursion:
When j = 0, then: P[i] [j] = T[i]; When j > 0, then: P[i] [j] = P[ P[i] [j1] ] [j1]
Since P[i] [j] is the (2^j)th ancestor of i, when j > 0, I think P[i][j] should be:
P[i] [j] = P[ P[i] [j1] ] [1]
Please correct me if I am wrong. Thank you.

