树上倍增

void dfs(int u, int f){
    deep[u] = deep[f] + 1;
    fa[u][0] = f;

    for(int i = 0; i < mp[u].size(); i++){
        int v = mp[u][i];
        if(v == f)    continue;
        dfs(v, u);
    }
}

void init(){
    int k = log(n*1.0)/log(2.0);
    for(int i = 1; i <= k; i++){
        for(int j = 1; j <= n; j++){
            fa[j][i] = fa[fa[j][i-1]][i-1];
        }
    }
}

int LCA(int u, int v){
    int i;
    if(deep[u] < deep[v])    swap(u, v);
    for(i = 0; (1 << i) <= deep[u]; i++);
    i--;
    for(int j = i; j >= 0; j--){
        if(deep[u] - (1 << j) >= deep[v])    u = fa[u][j];
    }
    if(u == v)    return u;
    for(int j = i; j >= 0; j--){
        if(fa[u][j] != fa[v][j]){
            u = fa[u][j];
            v = fa[v][j];
        }
    }
    return fa[u][0];
}