LCA(公共父节点)
求LCA的方式有许多，如一般解法，Tarjan，ST表等。这里介绍一下前两种。
- 问题概述
- 一般解法
- tarjan
问题概述：已知有一棵树求所问的每两个节点的公共父节点（深度最深），如图所示：求4，5的公共父节点，1和2都是但是相比下2的深度更深因此我们选择2。
题目链接：洛谷P3379
一般解法：
我们求两个节点的基本方法第一思路是从这两个节点往上找，找到第一个即可，如找4，5节点，我们往上翻第一个是2，那么就直接结束寻找，答案就是2。
因此我们就做一遍dfs记录一下各个节点的父节点即可，然后用一个dep数组记录一下节点的深度，因为这样更方便向上找的过程，我们首先要把深度深的节点给往上抬高，代码直接模拟就行：
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<vector>
5 #include<cstring>
6 #define inf 0x3f3f3f3f
7 using namespace std;
8 const int maxn = 1e5+10;
9 bool vis[maxn];
10 int fa[maxn],n,m,root,t1,t2;
11 int head[maxn],depth[maxn],cnt=0;
12 struct node{
13 int next,to;
14 }edge[maxn<<1];
15 void add(int p1,int p2)
16 {
17 edge[++cnt]=(node){head[p1],p2};head[p1]=cnt;
18 edge[++cnt]=(node){head[p2],p1};head[p2]=cnt;
19 }
20 void dfs(int point,int dep)
21 {
22 depth[point]=dep;
23 for(int i=head[point];i;i=edge[i].next)
24 {
25 if(vis[edge[i].to]) continue;
26 fa[edge[i].to]=point; vis[edge[i].to]=true;
27 dfs(edge[i].to,dep+1);
28 }
29 }
30 int ask(int p1,int p2)
31 {
32 if(depth[p1]<depth[p2]) swap(p1,p2);
33 while(depth[p1]>depth[p2]) p1=fa[p1];
34 while(p1!=p2) p1=fa[p1],p2=fa[p2];
35 return p1;
36 }
37 int main()
38 {
39 memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis));
40 memset(fa,0,sizeof(fa));
41 scanf("%d%d%d",&n,&m,&root);
42 fa[root]=root,vis[root]=1,depth[root]=1;
43 for(int i=1;i<n;i++)
44 {
45 scanf("%d%d",&t1,&t2);
46 add(t1,t2);
47 }
48 dfs(root,1);
49 while(m--)
50 {
51 scanf("%d%d",&t1,&t2);
52 printf("%d\n",ask(t1,t2));
53 }
54 return 0;
55 }
Tarjan：
上述的算法显而易见有个缺陷就是在查找的时候我们所用的时间复杂度是很高的，不合理。
Tarjan离线算法就是利用树的后续遍历这个特点，加上并查集的算法，我们先根据后续遍历去建立vis访问数组，当回溯的时候我们再去用并查集合并父亲，如上述的图所示4及它的节点都遍历完了这时要遍历5，如果有查询4，5的关系，因为4已经遍历了，所以它的父节点就是2，同时vis[4]标记也打了，这个时候答案就是find_fa(4)。因此总结来说，如果查询2个节点如果一个已经遍历了，那么查到另一个时答案就是find(bef)，我们配合树的性质就很好写出了。
1 #include<iostream>
2 #include<cstring>
3 #include<algorithm>
4 #include<vector>
5 #define inf 0x3f3f3f3f
6 using namespace std;
7 const int maxn = 1e5+10;
8 int n,m,root,t1,t2,cnt;
9 int fa[maxn],head[maxn];
10 int vis[maxn],in_degree[maxn];
11 vector<int> v[maxn];
12 struct edge{
13 int next,to;
14 }a[maxn];
15 inline int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
16 void add(int p1,int p2) {a[++cnt]=(edge){head[p1],p2}; head[p1]=cnt;}
17 void Union(int x,int y)
18 {
19 x=find(x); y=find(y);
20 if(x==y) return;
21 fa[y]=x;
22 }
23 void LCA(int point)
24 {
25 for(int i=head[point];i;i=a[i].next)
26 {
27 LCA(a[i].to);
28 Union(point,a[i].to);
29 }
30 vis[point]=1;
31 for(int i=0;i<v[point].size();i++)
32 if(vis[v[point][i]])
33 cout<<point<<" and "<<v[point][i]<<" = "<<find(v[point][i])<<endl;
34 }
35 int main()
36 {
37 std::ios::sync_with_stdio(false);
38 memset(head,0,sizeof(head));
39 memset(vis,0,sizeof(vis));
40 memset(in_degree,0,sizeof(in_degree));
41 cin>>n>>m;
42 for(int i=1;i<=n;i++) fa[i]=i;
43 for(int i=1;i<n;i++)
44 {
45 cin>>t1>>t2;
46 add(t1,t2); in_degree[t2]++;
47 }
48 while(m--)
49 {
50 cin>>t1>>t2;
51 v[t1].push_back(t2);
52 v[t2].push_back(t1);
53 }
54 for(int i=1;i<=n;i++)
55 if(!in_degree[i]) root=i;
56 LCA(root);
57 return 0;
58 }