LCA（tarjan）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

这是LCA算法中的一种，Tarjan算法

其实这么说也有点不对，应该是Tarjan+DFS进行解决

LCA又称为最近公共祖先

那么什么是最近公共祖先：

在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点

而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。

换句话说，最近公共祖先就是两个点在这棵树上距离最近的公共祖先节点。

那么我们该如何去求这个最近公共祖先呢？

通常初学者都会想到最简单粗暴的一个办法：

对于每个询问，遍历所有的点，时间复杂度为O(n*q)，很明显，n和q一般都是挺大的。

常用的求LCA的算法有：

Tarjan/DFS+ST/倍增

后两个算法都是在线算法，也很相似，时间复杂度在O(logn)~O(nlogn)之间

有的题目是可以用线段树来做的，但是其代码量很大，

况且时间复杂度也挺高，在O(n)~O(nlogn)之间，但是优点在于简单粗暴。

关于Tarjan算法：

1、 Tarjan算法是离线算法，需要预先读入所有的询问。

2、 Tarjan是基于并查集的。

3、这个Tarjan算法跟求桥求连通块那个tarjan算法不一样（事实上tarjan发明过很多算法，貌似都叫tarjan算法）

4.任选一个点为根节点，从根节点开始。

5.遍历该点u所有子节点v，并标记这些子节点v已被访问过。

6.若是v还有子节点，返回2，否则下一步。

7.合并v到u上。

8.寻找与当前点u有询问关系的点v。

9.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。

遍历就是用DFS，优化则是用并查集。

例题：

洛谷P3379

传送门

这题就可以用Tarjan算法进行求解

当然，和Tarjan在一起连用的就是DFS

代码挺难的，好多：

#include<cstdio>
#include<cstring>
using namespace std;
inline int read(){
int a; scanf("%d",&a);
return a;
}
const int N=5e5+;
int head[N],n,m,S,tot(),Qtot(),f[N],ans[N],Qhead[N];
bool vis[N];
struct E{int to,next;}e[N<<];
struct Q{int ver,next;}q[N<<];
inline void add_edge(int u,int v){
e[tot]=(E){
v,head[u]
};
head[u]=tot++;
e[tot]=(E){
u,head[v]
};
head[v]=tot++;
}
inline void add_query(int u,int v){
q[Qtot]=(Q){
v,Qhead[u]
};
Qhead[u]=Qtot++;
q[Qtot]=(Q){
u,Qhead[v]
};
Qhead[v]=Qtot++;
}
inline void add_ans(int A,int query_num){
ans[query_num>>]=A;
}
void print_ans(){
for(int i=;i<m;i++)
printf("%d\n",ans[i]);
}
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
inline void RAB()
{
n=read();
m=read();
S=read();
int u,v;
memset(head,-,sizeof(head));
for(int i=;i<n;i++)
u=read(),v=read(),add_edge(u,v);
memset(Qhead,-,sizeof(Qhead));
for(int i=;i<=m;i++)
u=read(),v=read(),add_query(u,v);
for(int i=;i<=n;i++)
f[i]=i;
memset(vis,true,sizeof(vis));
}
void dfs(int s,int fa)
{
for(int i=head[s],to=e[i].to;i!=-;i=e[i].next,to=e[i].to)
if(to!=fa)
dfs(to,s),f[find(to)]=s;
vis[s]=false;
for(int i=Qhead[s],ver=q[i].ver;i!=-;i=q[i].next,ver=q[i].ver)
if(!vis[ver]) add_ans(find(ver),i);
}
int main()
{
RAB();
dfs(S,);
print_ans();
return ;
}