Lowest Common Ancestor, O(N log N) pre-processing, O(log N) query time.

lca.cpp

#define MAXN 1005
#define MAXE 1005
#define MAXL 25

struct Node {
    int p, h;
};

Node V[MAXN];
vi E[MAXE];
int N, memo[MAXN][MAXL];

void dfs(int u, int depth, int parent) {
    V[u].h = depth;
    V[u].p = parent;

    for (int i = 0; i < E[u].size(); ++i) {
        int v = E[u][i];
        dfs(v, depth + 1, u);
    }
}

void preprocessing() {
    for (int i = 0; i < MAXN; ++i)
        for (int j = 0; j < MAXL; ++j)
            memo[i][j] = -1;
    
    for (int i = 0; i < N; ++i)
        memo[i][0] = V[i].p;

    for (int j = 1; (1 << j) <= N; ++j)
        for (int i = 0; i < N; ++i)
            if (memo[i][j - 1] != -1)
                memo[i][j] = memo[ memo[i][j-1] ][j-1];
}

int lca(int u, int v) {
    int tmp, log, i;

    if (V[u].h < V[v].h)
        swap(u, v);
    for (log = 1; (1 << log) <= V[u].h; ++log);
    --log;
    
    for (i = log; i >= 0; --i)
        if (V[u].h - (1 << i) >= V[v].h)
            u = memo[u][i];

    if (u == v) return u;

    for (i = log; i >= 0; --i) {
        if (memo[u][i] != -1 && memo[u][i] != memo[v][i])
            u = memo[u][i], v = memo[v][i];
    }

    return V[u].p;
}