向上标记法

树上倍增法 多次询问两个节点的公共祖先节点

F[x,k]表示节点x的第pow(2,k)辈祖先节点，即从x节点向根节点走pow(2,k)步到达的祖先节点,
递推公式：F[x,k]=F[F[x,k-1],k-1]
预处理阶段：O(nlogn)
（1）对深度较大的节点x，向上走n,n-1,...0步，检查是否比y节点更深。此时令x走到不比y更深的位置
若此时，d[x]==d[y]，则y即时最近公共祖先节点
当节点x与节点y处于同一深度时，同时向上走相同步数n，n-1,....,1,0

int t=(int)log(n)/log(2)+1;
//预处理
void bfs(){
    q.push(1);d[1]=1;
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=h[x];~i;i=ne[i]){
            int y=e[i];
            if(d[y]) continue;
            d[y]=d[x]+1;
            dist[y]=dist[x]+w[i];
            f[y][0]=x;
            for(int j=1;j<=t;j++){
                f[y][j]=f[f[y,j-1]][j-1];
            }
            q.push(y);
        }
    }
}

//查询x,y的最近公共祖先节点
int lca(int x,int y){
    if(d[x]>d[y]){
        swap(x,y);
        for(int i=t;i>=0;i--){
            if(d[f[y][i]]>=d[x]){
                y=f[y][i];
            }
        }
        if(x==y){
            return x;
        }
        for(int i=t;i>=0;i--){
            if(f[x][i]!=f[y][i]){
                x=f[x][i];
                y=f[y][i];
            }
        }
        return f[x][0];
    }
}

//回答问题
for(int i=1;i<=m;i++){
    int x,y;
    cin>>x>>y;
    cout<<dist[x]+dist[y]-2*(dist[lca(x,y)]<<endl;
}

Tarjan