决胜机房奥林匹克之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一样,且应用更广,但难度已经超过了我们的讨论范围,故不作介绍和学习。