##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(Column by column)
Build the table column by column. First, fill column (parents). Then fill column using column . Then fill column using column . And so on. For each column from to , and for each node , set:
up[v][j] = up[up[v][j-1]][j-1]
Time: , because you fill entries, each in time. Space: for the table. For , the table has about million entries.
