Dynamic Programming Sparse Matrix Approach populating 2 ^ i parent for each node Time complexity : O ( nlogn )
void precomputeSparseMatrix ( int n ) { for ( int i = 1 ; i < level ; i ++ ) { for ( int node = 1 ; node <= n ; node ++ ) { if ( parent [ node ] [ i - 1 ] != -1 ) parent [ node ] [ i ] = parent [ parent [ node ] [ i - 1 ] ] [ i - 1 ] ; } } }