需要知识

dfs序和并查集

伪代码 

tarjan(u) {
    for each(u, v) { // 枚举u的子节点v
        tarjan(v)
       merge(v, u) // 把v合并到u上
    vis[v] = 1
    }
    for each(u, v) // 枚举和u相关的询问
        if (vis[v])
            LCA(u, v) = find(v)
}

思路

总思路就是每进入一个节点u的深搜，就把整个树的一部分看作以节点u为根节点的小树，再搜索其他的节点。每搜索完一个点后，如果该点和另一个已搜索完点为需要查询LCA的点，则这两点的LCA为另一个点的现在的祖先。

1.先建立两个链表，一个为树的各条边，另一个是需要查询最近公共祖先的两节点。

2.建好后，从根节点开始进行一遍深搜。

3.先把该节点u的father设为他自己（也就是只看大树的一部分，把那一部分看作是一棵树），搜索与此节点相连的所有点v，如果点v没被搜索过，则进入点v的深搜，深搜完后把点v的father设为点u。

4.深搜完一点u后，开始判断节点u与另一节点v是否满足求LCA的条件，满足则将结果存入数组中。

5.搜索完所有点，自动退出初始的第一个深搜，输出结果。

举个栗子

图片说明
• 询问<E,G>, <F,D>, <K,J>的LCA
• f[]数组为并查集的父节点数组，初始化f[i] = i
• vis[]数组为是否访问过的数组，初始化为0
• A->B->E，发现E没有子节点，寻找与其相关的询问，发现有<E,G>，但是vis[G]=0，所以不操作，返回B，vis[E]=1,f[E]=B.
• 搜索F，发现有询问<F,D>，但是vis[D]=0，所以不操作，返回B，vis[F]=1, f[F]=B.
• 搜索G，发现有询问<E,G>，且vis[E]=1，得到LCA(E,G)=find(E)=B，然后返回B, vis[G]=1, f[G]=B.
• B搜索完毕，返回A，vis[B]=1, f[B]=A.
• A->C->H->C->A，vis[C]=vis[H]=1, f[H]=C, f[C]=A.
• A->D->I->K，发现询问<K,J>，但vis[J]=0，所以不操作，返回I，vis[K]=1, f[K]=I.
• 搜索L和M，无操作，f[L]=f[M]=I,vis[L]=vis[M]=1，返回I
• I搜索完了，返回D，f[I]=D, vis[I]=1
• 搜索J, 发现询问<K,J>，且vis[K]=1，得到LCA(K,J)=find(K)=D， 返回D.
• D搜索完了，发现询问<F,D>，且vis[F]=1，得到LCA(F,D)=find(F)=A, 返回A.
• A搜索完了，没有找到询问，算法结束.
• 我们在O(n + q)的时间复杂度内完美的解决了离线查询LCA问题。

Tarjan算法代码实现

• 树的存储结构： 

structedge{
int v,next;
}e[M];
int h[N],etot;

• 采用邻接链表来存树，其中h[]是头数组，e[]是边数组

• 添加边 

void add_edge(int x, int y){
e[etot].v =y;
e[etot].next =h[x];
h[x] = etot++;
}

• h[]初始化为-1，etot初始化为0

• 询问也要按照邻接链表存起来 

struct query{
int v, next,ans;
}q[M];
int Q[N],qtot;

• Q[]初始化为-1，qtot初始化为0

• 对于每一个询问(u, v)，调用add_query(u, v), add_query(v, u) 

void add_query(int u, int v){
q[qtot].v =v;
q[qtot].next =Q[u];
qtot++;
}

• 维护一个并查集，f[]记录每个点的父亲，初始f[i]=i 

int find(int x){
if (x == f[x]) returnx;
else return f[x] =find(f[x]);
}
void merge(int v, intu){
v =find(v);
u =find(u);
if (v != u) fa[v] =u;
}

• Tarjan算法主体，dfs的过程中合并父亲，回答询问。 

void tarjan(int u, int fa){
for (int i = h[u]; i != -1; i = e[i].next){
if (e[i].v != fa){
tarjan(e[i].v,u);
merge(e[i].v,u);
vis[e[i].v] =1;
}
}
for (int i = Q[u]; i != -1;i =q[i].next)
if(vis[[i].v])
q[i].ans =find(q[i].v);
}