Tarjan LCA

LCA的Tarjan算法的时间复杂度为O(n+q)是一种离线算法。

Tarjan求LCA的方法基于dfs与并查集

对于每一个点首先创建以本节点为父亲的并查集
然后分别访问子节点
返回时将子节点与当前结点合并

然后处理询问
对于每个节点u查找含有这个节点的询问
假设询问的点为v
看v是否被访问过
如果没有那么直接跳过等到遍历到 v 时直接可以找回来
如果遍历过 那么这个时候显然 LCA（u，v） == find( v )

举个例子（默认从左向右dfs遍历）
比如当前访问到11节点
发现询问中有（7，11）
这个时候7已经被访问过了而且fa值更新成了4
（因为这个时候还在遍历4的子树）
所以LCA（7，11）= 4

具体实现luogu LCA 3379：

const int maxn=500010<<1;
struct rec{
    int f,t,next,ans;
}e[maxn],ee[maxn];
int n=read(),m=read(),s=read(),p,now[maxn],fa[maxn],pp,head[maxn];
bool vis[maxn];
void add(int a,int b)
{
    p++;
    e[p].f=a;
    e[p].t=b;
    e[p].next=now[a];
    now[a]=p;
}
void addq(int a,int b)
{
    pp++;
    ee[pp].f=a;
    ee[pp].t=b;
    ee[pp].next=head[a];
    head[a]=pp;
}
int find(int x)
{
    return fa[x]==x ? x :fa[x]=find(fa[x]);
}
void tarjan(int x)
{
    fa[x]=x;
    vis[x]=1;
    for(int i=now[x];i;i=e[i].next)
    {
        int v=e[i].t;
        if(!vis[v]) 
        {
            tarjan(v);
            fa[find(v)]=x;
        }
    }
    for(int i=head[x];i;i=ee[i].next)
    {
        int v=ee[i].t;
        if(vis[v]){
            int k=i-1;
            ee[k].ans=ee[k^1].ans=find(v);
        }
    }
    return;
}
int main()
{
    //ios::sync_with_stdio(false);
    for(int i=1;i<n;i++)
    {
        int a=read(),b=read();
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=m;i++){
        int a=read(),b=read();
        addq(a,b);
        addq(b,a);
    }
    tarjan(s);
    for(int i=1;i<=pp;i+=2)
    {
        cout<<ee[i].ans<<"\n";
    //    cout<<ee[i].f<<" "<<ee[i].t<<endl;
    }
    return 0;
}

---

一些小细节：

• 读取询问的时候一定加双向边 保证能够在u访问不到v的情况下让v访问到u
• 加入询问边的时候可以在结构体里多开一个ans记录这次询问的结果
• 因为对于每次询问都记了两条编号相邻的边 因此当一次询问找到ans时要让ee[i].ans=ee[(i-1)^1].ans=lca（u，v）输出询问时就直接将编号每次+2就可以了

• 关于vis[ ]的位置：
  LL发现他每次找到答案就cnt++
  结果比输出结果要多
  意识到如果lca（u，v）= u or v 时就会这样

  比如当前访问到7
  有一个询问（7，4）
  显然4已经被vis了 这个时候cnt++
  然后遍历完子树返回到4的时候 又会有一个（4，7） cnt又++
  类似的情况都因为vis在遍历子树之前就被标记了
  所以
  只要把vis放到第一个for循环后边
  然后函数参数里边记一个father防止去掉vis后儿子访问父亲
  就可以保证每次询问只被更新一次

  

  所以呢
  还是用我一开始的存答案方法比较省事儿哈哈哈哈哈哈哈