LCA

/*
 * Algorithm : Lowest Common Ancestor ( Adapted From Topcoder )
 * Order : Pre-proccesing O( nlogn )
           Query O( logn )
 * Note : Node indexing must be 0 based
 */

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 100007
#define MAX_L 21
long N;
long Pre[MAX+7][MAX_L];
long Par[MAX+7];
long Lvl[MAX+7];

void Process( void )
{
    long i,j;
    for( i=0;i<N;i++ ){
        for( j=0;1<<j<N;j++ ) Pre[i][j] = -1;
    }
    for( i=0;i<N;i++ ) Pre[i][0] = Par[i];
    for( j=1;1<<j<N;j++ ){
        for( i=0;i<N;i++ ){
            if( Pre[i][j-1] != -1 ){
                Pre[i][j] = Pre[Pre[i][j-1]][j-1];
            }
        }
    }
}

long Query( long p,long q )
{
    long i,Log;

    /* If p is situated on a higher level than q then swap them */
    if( Lvl[p]<Lvl[q] ) swap( p,q );
    /* Compute the value of [log(Lvl[p)] */
    for( Log=1;1<<Log <= Lvl[p];Log++ );
    Log--;

    /* Find the ancestor of node p situated on the same level
       with q using the values in Pre */
    for( i=Log;i>=0;i-- ){
        if( Lvl[p] - (1<<i) >= Lvl[q] ) p = Pre[p][i];
    }
    if( p==q ) return p;

    /* Compute LCA(p, q) using the values in Pre */
    for( i=Log;i>=0;i-- ){
        if( Pre[p][i]!=-1 && Pre[p][i]!=Pre[q][i] ){
            p = Pre[p][i];
            q = Pre[q][i];
        }
    }
    return Par[p];
}