lca_ancestral.cpp

// declarar a tabela
ancestral[MAXN][MAXL]; // MAXL representa lg N (com uma margem a mais, claro)

// primeiro, inicializamos tudo para -1
for(int i = 0;i < MAXN;i++)
for(int j = 0;j < MAXL;j++)
    ancestral[i][j] = -1;

// definimos os pais de carda vértice
for(int i = 1;i <= N;i++) ancestral[i][0] = pai[i];

// montamos o restante da tabela com programação dinâmica
for(int j = 1;j < MAXL;j++)
for(int i = 1;i <=   N;i++)
    if(ancestral[i][j-1] != -1)
        ancestral[i][j] = ancestral[ ancestral[i][j-1] ][j-1];