» » Lowest Common Ancestor

Lowest Common Ancestor

   2:57 AM       

//<O(N logN, O(logN)>
#define mx 10010
#define logmx ceil(log(mx))
#define pii pair < int, int >
//#define i64 __int64
#define inf 2147483647

int L[mx], T[mx], P[mx][logmx];
const int root = 1;
bool color[mx];
long long d[mx];
vector < pii > G[mx];
void preprocess(int n){
    int i,j;
    for(i = 1; i <= n; i++)for(j = 0; (1<<j) < n; j++)P[i][j] = -1;
    for(i = 1; i <= n; i++)P[i][0] = T[i];
    for (j = 1; (1<<j) < n; j++)for (i = 1; i <= n; i++)
        if (P[i][j - 1] != -1)
            P[i][j] = P[P[i][j - 1]][j - 1];
}

int getLCA(int p, int q){
    int lg, i;
    if (L[p] < L[q])swap(p,q);
    for (lg = 1; (1<<lg) <= L[p]; lg++);
    lg--;
    for (i = lg; i >= 0; i--)
        if (L[p] - (1 << i) >= L[q])
            p = P[p][i];
    if (p == q)return p;
    for (i = lg; i >= 0; i--)
        if (P[p][i] != -1 && P[p][i] != P[q][i])
            p = P[p][i], q = P[q][i];
    return T[p];
}
Tutorial of Topcoder