决胜机房奥林匹克之LCA篇
决胜机房奥林匹克之LCA篇
前置知识：
二叉树
LCA：
https://www.luogu.com.cn/problem/P3379
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
LCA（Least Common Ancestors），即最近公共祖先，是指在有根树
中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科
比方说样例：
要你求3号点和2号点的lca。
显然，答案唯一，为根节点。
所以，lca有为一解，且必定有解。
那么，我们改如何去求解LCA呢？
暴力算法
考虑记录一下当前节点的深度。先让较深的那个节点跳到和另一个节点相同的深度（高度），再让两个节点一步一步地跳上去，直到跳到同意高度。
比方说，3号点和2号点求LCA的过程是：
三号点： 3 -> 1
二号点 2 -> 4 -> 1
code：
#include
using namespace std;
const int maxn = 500005;
#define int long long
vector p[maxn];
int f[maxn], dep[maxn];//dep记录深度，f[i]记录第i个点的父亲
void dfs(int x, int father){
// cout< dep[y]){
x = f[x];//让较深的那个节点跳到和另一个节点相同的深度（高度）
}
if(x == y){
return x;//注意这里如果已经求出答案了就直接return
}
while(x != y){
x = f[x], y = f[y];//两个点一起爬
}
return x;
}
signed main(){
int n, m, s;
cin>>n>>m>>s;
for(int i = 1; i < n; i++){
int x, y;
cin>>x>>y;
p[x].push_back(y);
p[y].push_back(x);
}
dfs(s, s); //注意根节点的父亲是它本身
for(int i = 1; i <= m; i++){
int x, y;
cin>>x>>y;
cout< 这玩意预处理\(O(n)\)，每次查询\(O(n)\),所以复杂度应该是\(O(nm)\)吧？
倍增优化
可以发现，一个一个地往上跳实在是太慢了！！，这就让我们有了优化空间。
我们学习了倍增这一神奇的算法。考虑往上跳的时候加入倍增的思想，按2的n次幂来调。
这里需要注意，我们倍增时应当从大到小来试而不是从小到大，即：
128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
而不是：1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128
另外，由于是按\(2^i\)来跳，所以需要记录下x的\(2^j\)级祖先。
举个例子：
我们来看如何求4和10的LCA。
10先跳到6。然后一起调到LCA的下一层。6跳到3，4跳到2。
这里要注意倍增是只跳到LCA的下一层，不然会出问题。
#include
using namespace std;
const int maxn = 500005;
int n, m, s;
vector adj[maxn];
int uu, vv;
int dep[maxn], f[maxn][20];
void dfs(int u, int p){
dep[u] = dep[p] + 1;
f[u][0] = p;
for(int i = 1; i < 20; ++i){
f[u][i] = f[f[u][i-1]][i-1];
}
for(int v: adj[u]) if(v != p) dfs(v, u);
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
for(int i = 19; i >= 0; --i){
if(dep[f[u][i]] >= dep[v]) u = f[u][i];
}
if(u == v){
return u;
}
for(int i = 19; i >= 0; i--){
if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
}
return f[u][0];
}
int main(){
cin>>n>>m>>s;
for(int i = 1; i <= n-1; i++){
int u, v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(s, s);
int q = m;
// int q;
// cin>>q;
int last = 0;
int u, v;
while(q--){
cin>>u>>v;
cout< 倍增算法的复杂度是\(O((n+m)logn)\)
Tarjan求LCA
这是一种非常高效的求LCA的方法，复杂度\(O(n+m)\)。它唯一的缺点是一个离线算法，所以有一定局限。然而学下来感觉跟tarjan没啥关系
我们要在树上进行dfs，在dfs的过程中。
- 对于一个我们搜过了的节点并且完成了回溯的节点我们把它标上2。
- 对于一个我们搜过了的节点但没完成了回溯的节点我们把它标上1。
- 自然，对于一个我们没搜过的节点我们就没有标记。
在上图中，黑色点代表标记1，灰色点代表标记2，白色点代表为标记。
对于正在访问的节点x，他到根节点的路径全部标为了黑。若y是灰点，则LCA(x,y) 就是y向上走到根为止，第一个遇到的黑点。
对于这样一个方法，我们姑且把它称为“向上标数法”。对于这个方法，我们考虑用并查集优化。当一个点被标为灰时，把它的集合并到它父亲的集合中去。可以发现，合并时它的父节点一定为黑点，且单独构成一个集合。
所以，我们只需要查询y所在并查集的祖先，即LCA(x,y)。
这是一种非常优美的算法！
这边给一个求树上所有点的LCA的异或和的代码：
#include
using namespace std;
const int maxn = 50005;
int n;
vector adj[maxn];
bool vis[maxn];
int f[maxn];
int ret;
int find(int x){
if(f[x] != x) return f[x] = find(f[x]);
return x;
}
void dfs(int u, int p){
for(int v = 1; v <= n; v++){
if(vis[v]) ret ^= find(v);
}
vis[u] = true;
for(int v:adj[u]){
if(v != p) dfs(v, u), f[v] = u;
}
}
int main(){
cin>>n;
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= n-1; i++){
int u, v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 1);
cout< 结语
LCA作为树上一个重要的知识点，其中所蕴含的知识点非常值得我们深究。求LCA的方法多种多样，除了上文介绍的几种方法外，还有几种方法，但只有树剖的复杂度跟Tarjan一样，且应用更广，但难度已经超过了我们的讨论范围，故不作介绍和学习。