LCA

void add(int u,int v){
    e[idx] = v;ne[idx] = head[u];head[u] = idx++;
}

void dfs(int u,int father){
    depth[u] = depth[father]+1;
    for(int i=0;i<=19;i++){
        f[u][i+1] = f[u][f[u][i]];
    }
    for(int i = head[u];i;i = ne[i]){
        int v = e[i];
        if( v == father) continue;
        f[v][0] = u;
        dfs(v,u);
    }
}

int LCA(int x,int y){
    if(depth[x] < depth[y]) swap(x,y);
    for(int i=20;i>=0;i--){
        if(depth[f[x][i]]>depth[y]) x = f[x][i];
        if(x==y) return x;
    }
    for(int i =20;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];  //x.y是深度不同且最浅的子节点
}