LCA(Tarjan)

时间复杂度：dfs为O(N)，dfs过程中处理所有查询对为O(M)，总时间复杂度O(N+M)

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=500010, maxm=500010;
int N, M, S, tot, h[maxn], v[maxn], fa[maxn], p_tot, p_h[maxn];

struct edge{  int t, nxt; }E[maxn<<1];                                      //链式前向星，用于存储树
void add_edge(int u, int v){ E[++tot].t=v; E[tot].nxt=h[u]; h[u]=tot; }

struct pair{  int s, t, lca, nxt;}P[maxm<<1];                               //链式前向星，用于存储查询对
void add_pair(int s, int t){ P[++p_tot].t=t; P[p_tot].s=s; P[p_tot].nxt=p_h[s]; p_h[s]=p_tot; }

inline int read()
{
    int s=0, w=1; char ch=getchar();
    while(ch<='0' || ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0' && ch<='9'){ s=s*10+ch-'0';    ch=getchar(); }
    return s*w;
}

int getfa(int k){ return fa[k]==k ? k : fa[k]=getfa(fa[k]); }               //并查集的查询，带路径压缩

void lca_tarjan(int x)
{
    v[x]=1, fa[x]=x;                                                        //x点已访问，设置其fa为自己，形成以x为根的一颗独立子树
    for(int i=h[x]; i; i=E[i].nxt)
        if(!v[E[i].t])  lca_tarjan(E[i].t), fa[E[i].t]=x;                   //递归结束后再建立x与x儿子的父子关系
    for(int i=p_h[x], y; i; i=P[i].nxt)                                     //查找与x有关的所有lca询问
        if(v[y=P[i].t]){                                                    //对于某个询问(x, y)，如果y已经访问过了，lca(x, y)=getfa(y)
            P[i].lca=getfa(y);
            if(i%2) P[i+1].lca=P[i].lca;                                    //P数组中pair是成对存入的，一个是(x, y), 一个是(y, x)
            else    P[i-1].lca=P[i].lca;
        }
}

int main(){
    N=read(); M=read(); S=read();
    for(int i=1, x, y; i<N;  i++){ x=read(); y=read(); add_edge(x, y); add_edge(y, x); }
    for(int i=1, a, b; i<=M; i++){ a=read(); b=read(); add_pair(a, b); add_pair(b, a); }
    lca_tarjan(S);
    for(int i=1; i<=p_tot; i++)
        if(i%2) printf("%d\n", P[i].lca);
    return 0;
}

LCA(Tarjan)

原文：https://www.cnblogs.com/lfyzoi/p/10531474.html