LCA离线tarjan算法模板

int find(int x) {
    if (x != fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void lca(int x) {
    fa[x]=x;
    f[x]=1;
    a[x].d=++Time;
    for (int e=head[x];e!=0;e=next[e]) {
        if (f[vet[e]]==0) {
            len[vet[e]]=len[x]+val[e];//计算到根节点长度
            lca(vet[e]);
            fa[vet[e]]=x;
        }
    }
    a[x].f=++Time;
    f[x]=2;
    for (int e=headq[x];e!=0;e=nextq[e])
        if (f[vetq[e]]==2) {
            int v=find(vetq[e]);//v为最近公共祖先
            if (a[x].f<=a[v].f || a[v].f==0)
                ans[e]=len[x]+len[vetq[e]]-2*len[v];//计算编号为e的询问
            else ans[e]=-1;
        }
}

//主程序中先将询问双向建边