资深光能
RT
资深光能
LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。
对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。
另一种理解方式是把T理解为一个无向无环图，而LCA(T,u,v)即u到v的最短路上深度最小的点。
这里给出一个LCA的例子：
对于T=<V,E>
V={1,2,3,4,5}
E={(1,2),(1,3),(3,4),(3,5)}
则有：
LCA(T,5,2)=1
LCA(T,3,4)=3
LCA(T,4,5)=3
实现
暴力枚举（朴素算法）
对于有根树T的两个结点u、v，首先将u，v中深度较深的那一个点向上蹦到和深度较浅的点，然后两个点一起向上蹦，直到蹦到同一个点，这个点就是u，v的最近公共祖先，记作LCA（u，v）。
但是这种方法的时间复杂度在极端情况下会达到O（n）。特别是有多组数据求解时，时间复杂度将会达到O（n*m）。
例：[1]
在当这棵树是二叉查找树的情况下，如下图：
那么从树根开始：
-
如果当前结点t 大于结点u、v，说明u、v都在t 的左侧，所以它们的共同祖先必定在t 的左子树中，故从t 的左子树中继续查找；
-
如果当前结点t 小于结点u、v，说明u、v都在t 的右侧，所以它们的共同祖先必定在t 的右子树中，故从t 的右子树中继续查找；
-
如果当前结点t 满足 u <t < v，说明u和v分居在t 的两侧，故当前结点t 即为最近公共祖先；
-
而如果u是v的祖先，那么返回u的父结点，同理，如果v是u的祖先，那么返回v的父结点。[2]
C++代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int query(Node t, Node u, Node v) {
int left = u.value;
int right = v.value;
//二叉查找树内，如果左结点大于右结点，不对，交换
if (left > right) {
int temp = left;
left = right;
right = temp;
}
while (true) {
//如果t小于u、v，往t的右子树中查找
if (t.value < left)
t = t.right; //如果t大于u、v，往t的左子树中查找
else if (t.value > right)
t = t.left;
else
return t.value;
}
}
运用DFS序
DFS序就是用DFS方法遍历整棵树得到的序列。
两个点的LCA一定是两个点在DFS序中出现的位置之间深度最小的那个点，
寻找最小值可以使用RMQ。
复杂度参考值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int tot, seq[N << 1], pos[N << 1], dep[N << 1];
// dfs过程，预处理深度dep、dfs序数组seq
void dfs(int now, int fa, int d) {
pos[now] = ++tot, seq[tot] = now, dep[tot] = d;
for (int i = head[now]; i; i = e[i].next) {
int v = e[i].to;
if (v == fa) continue;
dfs(v, now, d + 1);
seq[++tot] = now, dep[tot] = d;
}
}
int anc[N << 1][20]; // anc[i][j]表示i节点向上跳2^j层对应的节点
void init(int len) {
for (int i = 1; i <= len; i++)
anc[i][0] = i;
for (int k = 1; (1 << k) <= len; k++)
for (int i = 1; i + (1 << k) - 1 <= len; i++)
if (dep[anc[i][k - 1]] < dep[anc[i + (1 << (k - 1))][k - 1]])
anc[i][k] = anc[i][k - 1];
else
anc[i][k] = anc[i + (1 << (k - 1))][k - 1];
}
int rmq(int l, int r) {
int k = log(r - l + 1) / log(2);
return dep[anc[l][k]] < dep[anc[r + 1 - (1 << k)][k]] ? anc[l][k] : anc[r + 1 - (1 << k)][k];
}
int calc(int x, int y) {
x = pos[x], y = pos[y];
if (x > y) swap(x, y);
return seq[rmq(x, y)];
}
int lca(int a, int b) {
dfs(root, 0, 1); // root为树根节点的编号
init(0);
return calc(a, b);
}
倍增寻找（ST算法）
此算法基于动态规划。
用f[i][j]表示区间起点为j长度为2^i的区间内的最小值所在下标，通俗的说，就是区间[j, j + 2^i)的区间内的最小值的下标。
从定义可知，这种表示法的区间长度一定是2的幂，所以除了单位区间(长度为1的区间)以外，任意一个区间都能够分成两份，并且同样可以用这种表示法进行表示，
[j, j + 2^i)的区间可以分成
[j, j+2^(i-1))和[j+2^(i-1),j + 2^i)，于是
可以列出状态转移方程为： f[i][j]=RMQ( f[i-1][j], f[i-1][j+2^(i-1)] )。
f[m][n]的状态数目为n*m = nlogn，每次状态转移耗时O(1)，所以预处理总时间为O(nlogn)。
原数组长度为n，当[j, j + 2^i)区间右端点j + 2^i - 1 >n时如何处理？在状态转移方程中只有一个地方会下标越界，所以当越界的时候状态转移只有一个方向，即当j + 2^(i-1) > n 时，f[i][j] =f[i-1][j]。
求解f[i][j]的代码就不给出了，只需要两层循环的状态转移就搞定了。
f[i][j]的计算只是做了一步预处理，但是我们在询问的时候，不能保证每个询问区间长度都是2的幂，如何利用预处理出来的值计算任何长度区间的值就是我们接下来要解决的问题。
首先只考虑区间长度大于1的情况（区间长度为1的情况最小值就等于它本身），给定任意区间[a, b] (1 <= a < b <= n)，必定可以找到两个区间X和Y，它们的并是[a, b]，并且区间X的左端点是a，区间Y的右端点是b，而且两个区间长度相当，且都是2的幂，如图所示：
设区间长度为2^k，则X表示的区间为[a, a + 2^k)，Y表示的区间为(b - 2^k, b]，则需要满足一个条件就是X的右端点必须大于等于Y的左端点减一，即 a+2^k-1 >= b-2^k，则2^(k+1) >= (b-a+1), 两边取对数（以2为底），得 k+1 >= lg(b-a+1)，则k >= lg(b-a+1) - 1，k只要需要取最小的满足条件的整数即可( lg(x)代表以2为底x的对数 )。
仔细观察发现b-a+1正好为区间[a, b]的长度len，所以只要区间长度一定，k就能在常数时间内求出来。而区间长度只有n种情况，所以k可以通过预处理进行预存。
当lg(len)为整数时，k 取lg(len)-1，否则k为lg(len)-1 的上整（并且只有当len为2的幂时，lg(len)才为整数）。
我们注意到，在整个倍增查找LCA的过程中，从u到v的整条路径都被扫描了一遍。如果我们在倍增数组F[i][j]中再记录一些别的信息，就可以实现树路径信息的维护和查询
实现过程：
预处理：通过dfs遍历，记录每个节点到根节点的距离dist[u]，深度d[u]
init()求出树上每个节点u的2^i祖先p[u][i]
求最近公共祖先，根据两个节点的的深度，如不同，向上调整深度大的节点，使得两个节点在同一层上，如果正好是祖先结束，否则，将两个节点同时上移，查询最近公共祖先。
核心代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void dfs(int u) {
for(int i=head[u]; i!=-1; i=edge[i].next) {
int to=edge[i].to;
if(to==p[u][0])continue;
d[to]=d[u]+1;
dist[to]=dist[u]+edge[i].w;
p[to][0]=u; //p[i][0]存i的父节点
dfs(to);
}
}
void init()//i的2^j祖先就是i的（2^(j-1))祖先的2^(j-1)祖先
{
for(int j=1; (1<<j)<=n; j++)
for(int i=1; i<=n; i++)
p[i][j]=p[p[i][j-1]][j-1];
}
int lca(int a,int b) {
if(d[a]>d[b])swap(a,b); //b在下面
int f=d[b]-d[a]; //f是高度差
for(int i=0; (1<<i)<=f; i++)
//(1<<i)&f找到f化为2进制后1的位置，移动到相应的位置
if((1<<i)&f)b=p[b][i]; //比如f=5，二进制就是101,所以首先移动2^0祖先，然后再移动2^2祖先
if(a!=b) {
for(int i=(int)log2(N); i>=0; i--)
if(p[a][i]!=p[b][i]) //从最大祖先开始，判断a,b祖先，是否相同
a=p[a][i], b=p[b][i]; //如不相同，a b同时向上移动2^j
a=p[a][0]; //这时a的father就是LCA
}
return a;
}
ST算法可以扩展到二维，用四维的数组来保存状态，每个状态表示的是一个矩形区域中的最值，可以用来求解矩形区域内的最值问题。
Tarjan算法（离线算法）
离线算法，是指首先读入所有的询问（求一次LCA叫做一次询问），然后重新组织查询处理顺序以便得到更高效的处理方法。Tarjan算法是一个常见的用于解决LCA问题的离线算法，它结合了深度优先遍历和并查集，整个算法为线性处理时间。
Tarjan算法是基于并查集的，利用并查集优越的时空复杂度，可以实现LCA问题的O(n+Q)算法，这里Q表示询问 的次数。
同上一个算法一样，Tarjan算法也要用到深度优先搜索，算法大体流程如下：对于新搜索到的一个结点，首先创建由这个结点构成的集合，再对当前结点的每一个子树进行搜索，每搜索完一棵子树，则可确定子树内的LCA询问都已解决。其他的LCA询问的结果必然在这个子树之外，这时把子树所形成的集合与当前结点的集合合并，并将当前结点设为这个集合的祖先。之后继续搜索下一棵子树，直到当前结点的所有子树搜索完。这时把当前结点也设为已被检查过的，同时可以处理有关当前结点的LCA询问，如果有一个从当前结点到结点v的询问，且v已被检查过，则由于进行的是深度优先搜索，当前结点与v的最近公共祖先一定还没有被检查，而这个最近公共祖先的包涵v的子树一定已经搜索过了，那么这个最近公共祖先一定是v所在集合的祖先。
如图：
根据实现算法可以看出，只有当某一棵子树全部遍历处理完成后，才将该子树的根节点标记为黑色（初始化是白色），假设程序按上面的树形结构进行遍历，首先从节点1开始，然后递归处理根为2的子树，当子树2处理完毕后，节点2， 5， 6均为黑色；接着要回溯处理3子树，首先被染黑的是节点7（因为节点7作为叶子不用深搜，直接处理），接着节点7就会查看所有询问(7, x)的节点对，假如存在(7, 5)，因为节点5已经被染黑，所以就可以断定(7, 5)的最近公共祖先就是find(5).ancestor，即节点1（因为2子树处理完毕后，子树2和节点1进行了union，find(5)返回了合并后的树的根1，此时树根的ancestor的值就是1）。有人会问如果没有(7, 5)，而是有(5, 7)询问对怎么处理呢? 我们可以在程序初始化的时候做个技巧，将询问对(a, b)和(b, a)全部存储，这样就能保证完整性。
参考代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
const int mx = 10000; //最大顶点数
int n, root; //实际顶点个数，树根节点
int indeg[mx]; //顶点入度，用来判断树根
vector<int> tree[mx]; //树的邻接表（不一定是二叉树）
void inputTree() //输入树
{
scanf("%d", &n); //树的顶点数
for (int i = 0; i < n; i++) //初始化树，顶点编号从0开始
tree[i].clear(), indeg[i] = 0;
for (int i = 1; i < n; i++) //输入n-1条树边
{
int x, y;
scanf("%d%d", &x, &y); //x->y有一条边
tree[x].push_back(y);
indeg[y]++;//加入邻接表，y入度加一
}
for (int i = 0; i < n; i++) //寻找树根，入度为0的顶点
if (indeg[i] == 0)
{
root = i;
break;
}
}
vector<int> query[mx]; //所有查询的内容
void inputQuires() //输入查询
{
for (int i = 0; i < n; i++) //清空上次查询
query[i].clear();
int m;
scanf("%d", &m); //查询个数
while (m--)
{
int u, v;
scanf("%d%d", &u, &v); //查询u和v的LCA
query[u].push_back(v);
query[v].push_back(u);
}
}
int father[mx], rnk[mx]; //节点的父亲、秩
void makeSet() //初始化并查集
{
for (int i = 0; i < n; i++) father[i] = i, rnk[i] = 0;
}
int findSet(int x) //查找
{
if (x != father[x]) father[x] = findSet(father[x]);
return father[x];
}
void unionSet(int x, int y) //合并
{
x = findSet(x), y = findSet(y);
if (x == y) return;
if (rnk[x] > rnk[y]) father[y] = x;
else father[x] = y, rnk[y] += rnk[x] == rnk[y];
}
int ancestor[mx]; //已访问节点集合的祖先
bool vs[mx]; //访问标志
void Tarjan(int x) //Tarjan算法求解LCA
{
for (int i = 0; i < tree[x].size(); i++)
{
Tarjan(tree[x][i]); //访问子树
unionSet(x, tree[x][i]); //将子树节点与根节点x的集合合并
ancestor[findSet(x)] = x;//合并后的集合的祖先为x
}
vs[x] = 1; //标记为已访问
for (int i = 0; i < query[x].size(); i++) //与根节点x有关的查询
if (vs[query[x][i]]) //如果查询的另一个节点已访问，则输出结果
printf("%d和%d的最近公共祖先为：%d\n", x,
query[x][i], ancestor[findSet(query[x][i])]);
}
int main()
{
inputTree(); //输入树
inputQuires();//输入查询
makeSet();
for (int i = 0; i < n; i++)
ancestor[i] = i;
memset(vs, 0, sizeof(vs));
//初始化为未访问
Tarjan(root);
}
树链剖分（树剖算法）
对于输入的这棵树，先对其进行树链剖分处理。显然，树中任意点对(u,v)只存在两种情况：
1. 两点在同一条重链上。
2. 两点不在同一条重链上。
对于1，LCA(u,v) 明显为u,v两点中深度较小的点，即min(deep[u],deep[v])。
对于2，我们只要想办法将u,v两点转移到同一条重链上即可。
所以，我们可以将u,v一直上调，每次将u,v调至重链顶端，直到u,v两点在同一条重链上即可。
核心代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
const int N=500004;
int head[N*2],next[N*2],to[N*2];// 树的邻接表
int deep[N],fa[N];// deep表示节点深度，fa表示节点的父亲
int size[N],son[N],top[N];// size表示节点所在的子树的节点总数
// son表示节点的重孩子
// top表示节点所在的重链的顶部节点
inline void add(int u,int v,int tnt)// 邻接表加边
{
nt[tnt]=ft[u];
ft[u]=tnt;
ed[tnt]=v;
}
void DFS(int u,int Fa)// 第一遍dfs，处理出deep，size，fa，son
{
size[u]=1;
for(int i=head[u];i;i=next[i])
{
if(to[i]==Fa)
continue;
deep[to[i]]=d[u]+1;
fa[to[i]]=u;
DFS(to[i],u);
size[u]+=size[to[i]];
if(size[to[i]]>size[son[u]])
son[u]=to[i];
}
}
void Dfs(int u)// 第二遍dfs，将所有相邻的重边连成重链
{
if(u==son[fa[u]])
top[u]=top[fa[u]];
else
top[u]=u;
for(int i=head[u];i;i=next[i])
if(to[i]!=fa[u])
Dfs(to[i]);
}
int LCA(int u,int v)// 处理LCA
{
while(top[u]!=top[v])// 如果u,v不在同一条重链上
{
if(deep[top[u]]>deep[top[v]])// 将深度大的节点上调
a=fa[top[u]];
else
b=fa[top[v]];
}
return deep[u]>deep[v]?v:u;// 返回深度小的节点（即为LCA(u,v)）
}
附并查集介绍
讲个简单的故事来加深对并查集的理解，这个故事要追溯到北宋年间。话说北宋时期，朝纲败坏，奸臣当道，民不聊生。又有外侮辽军大举南下，于是众多能人异士群起而反，各大武林门派同仇敌忾，共抗辽贼，为首的自然是中原武林第一大帮-丐帮，其帮主乃万军丛中取上将首级犹如探囊取物、泰山崩于前而面不改色的北乔峰；与其齐名的是空有一腔抱负、壮志未酬的南慕容带领的慕容世家；当然也少不了天下武功的鼻祖-少林，以及一些小帮派，如逍遥派、灵鹫宫、无量剑、神农教等等。我们将每个门派（帮派）作为一个集合，从中选出一个代表作为这个集合的标识，姑且认为门派（帮派）的掌门（帮主）就是这个代表。
作者有幸成了“抗辽联盟”的统计员，统计员只有一个工作，就是接收一条条同门数据，然后统计共有多少个门派，好进行分派部署。同门数据的格式为(x, y)，表示x和y属于同一个门派，接收到一条数据，需要对x所在的群体和y的群体进行合并，当统计完所有数据后有多少个集合就代表多少个门派。
这个问题其实隐含了两个操作：1、查找a和b是否已经在同一个门派；2、如果两个人的门派不一致，则合并这两个人所在集合的两堆人。分别对应了并查集的查找和合并操作。
如图所示，分别表示丐帮、少林、逍遥、大理段氏四个集合。[3]
重要结论
若树上两点(u,v)的路径长度为Long[u,v]，
long[i]表示i到root的长度，
则Long[u,v] = long[u]+long[v]-2*long[lca(u,v)]
缔造者之神
1
