LCA

vector <int> g[mx];
int T[mx], P[mx][22], L[mx];

void dfs(int from,int u,int dep){
    T[u]=from;
    L[u]=dep;
    for(int i=0;i<(int)g[u].size();i++){
        int v = g[u][i];
        if(v==from) continue;
        dfs(u,v,dep+1);
    }
}

int lca_query(int N, int p, int q){
    if (L[p] < L[q]) swap(p, q);
    int log = 1;
    while(1){
        int next=log+1;
        if((1<<next)>L[p])break;
        log++;
    }
    for(int i=log;i>=0;i--){
        if (L[p] - (1 << i) >= L[q]){
            p = P[p][i];
        }
    }

    if (p == q)
        return p;

    for(int i = log; 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];
}

int qthparetn(int N, int p, int q){
    int log = 1;
    while(1){
        int next=log+1;
        if((1<<next)>L[p])break;
        log++;
    }
    for(int i = log; i >= 0; i--){
        if((1<<i)<=q){
            p = P[p][i];
            q -= (1<<i);
        }
    }
    return p;
}

int dis(int a, int b, int n){
    int c = lca_query(n, a, b);
    return L[a] + L[b] - 2*L[c];
 }

void lca_init(int N){
    memset (P,-1,sizeof(P));
    dfs(-1, 0, 0);
    for(int i = 0; i < N; i++){
        P[i][0] = T[i];
    }
    for(int j=1;1<<j<N;j++){
        for(int i=0;i<N;i++){
            if(P[i][j-1]!=-1){
                P[i][j] = P[P[i][j-1]][j-1];
            }
        }
    }
 }