LCA算法模板

LCA算法简介：

对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。
LCA主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径。
LCA算法分为离线算法和在线算法
离线算法( off line algorithms)，是指基于在执行算法前输入数据已知的基本假设，也就是说，对于一个离线算法，在开始时就需要知道问题的所有输入数据，而且在解决一个问题后就要立即输出结果。
在线算法是指它可以以序列化的方式一个个的处理输入，也就是说在开始时并不需要已经知道所有的输入。
LCA的离线算法主要指的是基于深度优先搜索的tarjan算法

Tarjan求LCA的基本思路:

Step 1.任选一个点为根节点，从根节点开始。
Step 2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。
Step 3.若是v还有子节点，返回2，否则下一步。
Step 4.合并v到u上。
Step 5.寻找与当前点u有询问关系的点v。
Step 6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。

例题详解：洛谷P3379【模板】最近公共祖先（LCA）https://www.luogu.com.cn/problem/P3379

核心代码如下：

 1 int Find(int u){//查找节点 u 的祖先节点 
 2     if(f[u] == u) return f[u];
 3     return f[u] = Find(f[u]);
 4 }
 5 void Tarjan(int u){
 6     vis[u] = 1;//表示节点 u 正在访问中 
 7     f[u] = u;//先给 f 数组赋上初始值，即为节点本身 
 8     for(int i = head1[u]; i; i = e1[i].next){
 9         int v = e1[i].to;
10         if(!vis[v]){//节点 v 没访问过则访问节点 v  
11             Tarjan(v);
12             f[v] = u;//回溯时将 f[v] 更改为其父亲节点 
13         }
14     }
15     vis[u] = -1;//标记节点 u 已访问 
16     for(int i = head2[u]; i; i = e2[i].next){
17         int v = e2[i].to;
18         if(vis[v] == -1) ans[(i + 1) / 2] = Find(v);//若节点 v 已变黑，则询问 v 的祖先，因为第1条边和第2条边相当于是同一条边，我们这里写成(i + 1）/ 2 将他们的祖先存放于同一数组中 
19     }
20 }

在这里我们用一个 f 数组表示节点 u 的父亲节点，vis 数组表示节点 u 的访问情况，若 vis[u] = 1 则表示节点 u 正在访问中，若 vis[u] = -1 则表示节点 u 已访问，若 vis[u] = 初始值0 则表示节点 u 还未访问。具体解释见代码。

下面是完整代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 5e5 + 5;
 4 struct Edge{
 5     int to, next;
 6 }e1[maxn << 1], e2[maxn << 1];//左移1表示 * 2 
 7 int n, root, q;
 8 int f[maxn];
 9 int head1[maxn], head2[maxn], len1, len2;
10 void Insert(int u, int v, Edge e[], int head[], int &len){
11     e[++len].to = v;
12     e[len].next = head[u];
13     head[u] = len;
14 }
15 void Read(){
16     scanf("%d%d%d", &n, &q, &root);
17     for(int i = 1; i < n; ++i){
18         int u, v;
19         scanf("%d%d", &u, &v);
20         Insert(u, v, e1, head1, len1); 
21         Insert(v, u, e1, head1, len1);
22     }
23     for(int i = 1; i <= q; ++i){
24         int u, v;
25         scanf("%d%d", &u, &v);
26         Insert(u, v, e2, head2, len2); //给询问的边建立邻接表关系便于进行询问 
27         Insert(v, u, e2, head2, len2);
28     }
29 }
30 int vis[maxn];
31 int ans[maxn];
32 int Find(int u){//查找节点 u 的祖先节点 
33     if(f[u] == u) return f[u];
34     return f[u] = Find(f[u]);
35 }
36 void Tarjan(int u){
37     vis[u] = 1;//表示节点 u 正在访问中 
38     f[u] = u;//先给 f 数组赋上初始值，即为节点本身 
39     for(int i = head1[u]; i; i = e1[i].next){
40         int v = e1[i].to;
41         if(!vis[v]){//节点 v 没访问过则访问节点 v  
42             Tarjan(v);
43             f[v] = u;//回溯时将 f[v] 更改为其父亲节点 
44         }
45     }
46     vis[u] = -1;//标记节点 u 已访问 
47     for(int i = head2[u]; i; i = e2[i].next){
48         int v = e2[i].to;
49         if(vis[v] == -1) ans[(i + 1) / 2] = Find(v);//若节点 v 已变黑，则询问 v 的祖先，因为第1条边和第2条边相当于是同一条边，我们这里写成(i + 1）/ 2 将他们的祖先存放于同一数组中 
50     }
51 }
52 void Print(int a[], int n){
53     for(int i = 1; i <= n; ++i)
54         printf("%d/n", a[i]);
55 }
56 int main(){
57     Read();
58     Tarjan(root);//从根节点开始查询 
59     Print(ans, q);
60     return 0;
61 }

完结撒花