作为一名合格的 OIer ，一定要有自我总结的意识，一定要通过写博客的方式来验证自己的掌握程度
————沃.茨基硕德
目录
作为一名合格的 OIer ，一定要有自我总结的意识，一定要通过写博客的方式来验证自己的掌握程度————沃.茨基硕德写在前面0. 一些定义1. 暴力爬山法方法举个栗子
核心代码:
2.基于倍增的暴力爬山法方法预处理倍增优化-第一部分倍增优化-第二部分
代码
3.Tarjan算法方法举个栗子
代码
今天，咱们来讲一讲LCA算法
写在前面
对于LCA，笔者也并没有说做到百分之百的掌握掌握了就不用写博客了呀，所以若有什么错误的地方，希望各位看官可以指出；
0. 一些定义
首先，我们需要明白一些定义，这些定义可以帮我们更好的理解算法
祖先：有根树中，一个节点到根的路径上的所有节点被视为这个点的祖先，包括根和它本身；公共祖先：对于点a和b，如果c既是a的祖先又是b的祖先，那么c是a和b的公共祖先;深度：子节点的深度=父节点深度+1，一般我们定根的深度为1;最近公共祖先：树上两个节点的所有公共祖先中，深度最大的那个称为两个点的最近公共祖先(LCA的定义)。
好了，对于LCA的学习前提条件，各位看官已经明白了，那么接下来就正式进入LCA的讲解
1. 暴力爬山法
这个方法就和他的名字一样，暴力，变态但确实简单 如下图： 虽然有点丑将就看吧
方法
如果a和b的深度不同，那么将深度更大的那个点向根的方向移动一步(即选择它的父节点)，重复这个过程直到两个点深度相同;当a和b深度相同，但不是同一个点，那么各自向根的方向移动一步(即选择它们各自的父节点)，重复这过程直到选择到同一个点。
举个栗子
那让我们来尝试一下这个方法吧！
假设我们现在要找5和7的LCA：
第一步，找到每一个点的深度(DFS);
第二步，发现7的深度比5大，所以把7换成他的父亲节点4；
第三步，5和4的深度相同，但它们不是同一个点，所以把5换成3，6也换成3；
第四步，发现3和3是相同的店，所以LCA(5，7)=3；
核心代码:
int LCA(int a
,int b
){
while(dis
[a
]!=dis
[b
]){
if(dis
[a
]<dis
[b
])
b
=fa
[b
];
else
a
=fa
[a
];
}
while(a
!=b
){
a
=f
[a
],b
=f
[b
];
}
return a
;
}
各位客官，是否发现暴力爬山法的时间复杂度是O(n)呢？
我们将这棵树退化成一条链，查询的两点一个为根节点，另一个为叶子节点，这样的时间复杂度就退化成了 O(n)，如果我们查询q次，它的复杂度就是O(nq);
但聪明的客官是否发现，我们可以将它升级成O(nlogn)呢？
这就是第二种方法了。
2.基于倍增的暴力爬山法
方法
对于第一个部分，假设a的深度小于b，那么我们在做的事实际上就是找到b的祖先中深度和a一样的点c。
对于第二个部分，我们做的事就是找到a和c的LCA，假设是点d。
这两个部分都可以运用倍增的思想优化。
预处理
先求出每个点往根的方向走2的幂步的点，和快速幂中求a的次方类似。
如果我们以dp[i][j]表示从i往根方向走2j步的节点，那么也就等于从dp[i][j-1]再往根的方向走2(j-1)步的结果，即dp[i][j]=dp[dp[i][j-1]][j-1]。
可以在bfs求树上每个点深度的时候，顺便预处理fa数组，时间复杂度o(nlogn)。
一般如果走的步数超过到根的步数，一般设结果为0，因为一般点的编号不包0。
倍增优化-第一部分
我们从大到小枚举i，考虑往根的方向走2^i步之后深度会不会小于c的深度，也就是a的深度，如果不会就选择走，反之就选择不走。
时间复杂度o(logn)。
倍增优化-第二部分
假设点a、c和点d的深度差为dis，只要走的步数大于等于dis，那么a和c走的结果肯定是同一个点，所以先走dis-1步，再走一步。
所以我们要先判断现在的a和c是不是相同，如果不相同， 就先走到不相同的深度最小的点，再走一步。
同样，从大到小枚举i，每次走2^i步。
时间复杂度o(logn)。
代码
#include <bits/stdc++.h>
using namespace std
;
const int Step
= 20;
int n
, m
;
vector
<int> v
[100005];
bool f
[100005];
int pre
[100005];
int dp
[100005][30];
void BFS(int root
) {
queue
<int> q
;
q
.push(root
);
pre
[root
] = 1;
while (!q
.empty()) {
int x
= q
.front();
q
.pop();
for (int i
= 0; i
< v
[x
].size(); i
++) {
int y
= v
[x
][i
];
if (pre
[y
])
continue;
dp
[y
][0] = x
;
pre
[y
] = pre
[x
] + 1;
for (int j
= 1; j
<= Step
; j
++) {
dp
[y
][j
] = dp
[dp
[y
][j
- 1]][j
- 1];
}
q
.push(y
);
}
}
}
int LCA(int x
, int y
) {
if (pre
[x
] > pre
[y
]) {
int t
= x
;
x
= y
;
y
= t
;
}
for (int i
= Step
; i
>= 0; --i
) {
if (pre
[dp
[y
][i
]] >= pre
[x
])
y
= dp
[y
][i
];
}
if (x
== y
)
return x
;
for (int i
= Step
; i
>= 0; --i
) {
if (dp
[x
][i
] != dp
[y
][i
]) {
x
= dp
[x
][i
];
y
= dp
[y
][i
];
}
}
return dp
[x
][0];
}
int main() {
cin
>> n
>> m
;
for (int i
= 1; i
< n
; i
++) {
int x
, y
;
scanf("%d%d", &x
, &y
);
v
[x
].push_back(y
);
v
[y
].push_back(x
);
}
BFS(1);
for (int i
= 1; i
<= m
; i
++) {
int x
, y
;
scanf("%d%d", &x
, &y
);
printf("%d\n", LCA(x
, y
));
}
return 0;
}
3.Tarjan算法
方法
Tarjan算法本质上是用并查集的路径压缩优化的dfs，时间复杂度为O(N + Q)。
在DFS的任意时刻，树中节点分为两类：
已经开始递归的节点；尚未访问的节点。
我们可以定义一个布尔类型的数组f，在这些1类上标记一个整数1，2类节点暂时不管。
在DFS的回溯时，我们可以把回溯点的并查集中的祖先设为他的父节点
那么对于任何两个点来说，如果两个点都被递归遍历过，那么他们的LCA就是两个点并查集中的祖先。
举个栗子
我们来找6和10的LCA；
搜索，将f[2]设为1；f[3]=1;f[4]=1;f[6]=1，发现查询中有6,但又发现10并未被查询(即f[10]=0),所以暂时不管；6为叶子节点，回溯，并让pre[6]=4;f[7]=1;7为叶子节点，回溯，并让pre[7]=4;4所有节点都遍历过了，回溯，并让pre[4]=3;f[5]=1;……f[10]=1,发现查询中有10，且6已被查询过(f[6]=1)，所以LCA(6,10)=Find_Set(6)=3;
代码
#include <bits/stdc++.h>
using namespace std
;
struct zz
{
int u
, id
;
};
vector
<int> v
[100005];
vector
<zz
> sum
[100005];
int n
, m
;
int ans
[100005];
int pre
[100005];
bool f
[100005];
int Find_Set(int x
) {
if (x
!= pre
[x
]) {
pre
[x
] = Find_Set(pre
[x
]);
}
return pre
[x
];
}
void Make_Set(int x
) {
for (int i
= 1; i
<= x
; i
++) {
pre
[i
] = i
;
}
}
void Tarjan(int x
) {
f
[x
] = 1;
for (int i
= 0; i
< v
[x
].size(); i
++) {
int y
= v
[x
][i
];
if (f
[y
])
continue;
Tarjan(y
);
pre
[y
] = Find_Set(x
);
}
for (int i
= 0; i
< sum
[x
].size(); i
++) {
zz y
= sum
[x
][i
];
if (f
[y
.u
] == 1) {
ans
[y
.id
] = Find_Set(y
.u
);
}
}
}
int main() {
cin
>> n
>> m
;
Make_Set(n
);
for (int i
= 1; i
< n
; i
++) {
int x
, y
;
scanf("%d%d", &x
, &y
);
v
[x
].push_back(y
);
v
[y
].push_back(x
);
}
for (int i
= 1; i
<= m
; i
++) {
int x
, y
;
scanf("%d%d", &x
, &y
);
sum
[x
].push_back(zz
{ y
, i
});
sum
[y
].push_back(zz
{ x
, i
});
}
Tarjan(1);
for (int i
= 1; i
<= m
; i
++) {
printf("%d\n", ans
[i
]);
}
return 0;
}
