二进制分组与LCA

本文介绍倍增法求LCA

例题HDOJ2586

例题题意

抽象一下 题目给了一棵树 要求给出的两个节点之间的简单路径的距离
在给出算法之前 我们先介绍一下LCA

LCA的含义

LCA(Lowest Common Ancestor)最近公共祖先 指的是在一棵树中距离某两个节点最近的祖先节点(顾名思义)

例题分析

题意很容易理解 也不难想到一般的暴力做法 比如跑一遍最短路啥的(ps:这题最短路是能过的 数据有点水)
不过我们这里用LCA来解决
容易想到的做法是:
记p是u和v节点的LCA 那么答案就是dis(u,p)+dis(v,p) 这是很容易理解的
那么下一步我们就是求u v节点的LCA

LCA的实现

首先我们方法有很多 比如暴力

暴力实现

u节点和v节点同时向自己的父亲节点跳 并打vis标记 如果某一个节点p被重复打标记 那么这个p就是LCA
然而 暴力的方法理解起来简单 但也有他的局限性 首先 这个方法最坏是O(n)的(考虑一条链状的树)时间复杂度很高 如果询问组数比较多 大部分情况是过不了题的

优化

回顾一下背包问题:
有n种物品$a_1 a_2…a_n$每种物品都有不同的数量$b_1 b_2…b_n$和不同的价值$c_1 c_2…c_n$ 问 容量为m的背包最多能装多少价值的物品?
关于背包问题的解法就不做具体介绍了(dp) 关键是这里的一个关键的优化采用了二进制分组的想法:
对物品$a_i$分组 $1/2/4/8/…/2^n$ 捆绑每一个组的物品变成一个新的物品 然后把问题规约成一个01背包问题 这比直接把原问题当作01背包来处理会快很多
原理是这样的:
每一个十进制数可以表示成一系列2幂次数的和 因为$x=(\overline{b_0b_1...b_n})_{2}=\sum_{i=0}^n{b_i\cdot2^i}$
那么在LCA问题下 每次只要往上跳$2^i$的距离即可 复杂度降到了对数级别

具体实现

  1. 一遍dfs求出每一个节点的深度depth[] 并预处理出up[][]数组 up[i][j]表示i节点往上跳$2^j$的节点
  2. 处理询问 假设节点u的深度大于v的深度 先把u节点跳到和v相同深度
    1. 如果u==v 说明询问的两个节点在同一条树链上 直接返回u 算法结束
    2. 如果u!=v 说明询问的两个节点不在同一条树链上 u v开始同时向上跳 注意一点 当两个节点向上跳$2^i$以后位于不同的节点才执行跳的操作(原因后面会说)
  3. 此时u和v同时向上跳1个节点就达到LCA节点了 算法结束

整个算法过程中向上跳的操作 都从长距离向短距离跳 即先跳$2^i$ 再跳$2^{i-1}$ 再跳$2^{i-2}$…

算法中的细节

Q1:
为什么3.2.中说“当两个节点向上跳$2^i$以后位于不同的节点才执行跳的操作”?
A1:
首先我们在向上跳的时候不能跳过lca节点了 不然找不到lca了
如果up[u][i]==up[v][i]就说明跳过了或者到达了lca节点

Q2:
为什么第四步中u和v同时向上跳1个节点就到达lca了?
A2:
这是一个小trick 其实这里用while循环一个一个往上跳也是没有问题的 不过还是循环体内顶多执行一次
假设LCA和u(v)的距离为c 注意到 c-1一定可以被二进制分组 那么遵循从长距离向短距离跳的原则 并且u和v不会跳到LCA及LCA上面去 那么过程中一定会跳到LCA节点的儿子节点 并在这里停住不会再往上跳直到3.结束 因此 4.中u和v直接向上跳1个节点就是LCA了

Q3:
怎么处理up数组?
A3:
由于$2^i=2^{i-1}+2^{i-1}$
假设在处理up[v]数组的时候我们预先已经处理好了up[ansestor of v]数组 那么up[v][i]=up[up[v][i-1]][i-1]

Q4:
预处理?
A4:
在询问组数比较多的情况下 预处理是必须的 预处理的复杂度是$O(n)$->即dfs的复杂度 在之后向上跳的复杂度是$O(1)$的
当然如果只有一次询问 请选择直接用以上说的直接暴力做法 复杂度是$O(n)$的 和预处理复杂度相差无几 但是码短

算法复杂度

假设一共是n个节点 m组询问
dfs的复杂度是$O(n)$ 处理每一组询问的复杂度是$O(\log n)$
所以总复杂度是$O(n+m\log n)$

例题代码

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>

using namespace std;
const int N=40000+10;
const int TP=32;

struct Edge{
int from,to,cost;
Edge(int from,int to,int cost):from(from),to(to),cost(cost){}
Edge(){}
};

int n,m;
vector<Edge> edges;
vector<int> g[N];
int depth[N],up[N][TP];
int len[N][TP];

inline void clearall(){
for(int i=1;i<=n;i++) g[i].clear();
edges.clear();
}

inline void addedge(int from,int to,int cost){
edges.push_back(Edge(from,to,cost));
g[from].push_back(edges.size()-1);
}

//题目要求两点间距 所以在dfs的时候追加预处理len数组
//len[i][j]表示i节点向上跳2^j的距离
void dfs(int v,int fa){
up[v][0]=fa;
for(int i=1;i<TP;i++){
if(up[v][i-1]==-1) break;
up[v][i]=up[up[v][i-1]][i-1];
len[v][i]=len[v][i-1]+len[up[v][i-1]][i-1];
}
for(int i=0;i<g[v].size();i++){
auto &e=edges[g[v][i]];
if(e.to!=fa){
depth[e.to]=depth[v]+1;
len[e.to][0]=e.cost;
dfs(e.to,v);
}
}
}

inline void init(){
memset(up,-1,sizeof(up));
memset(len,0,sizeof(len));
depth[1]=1;
dfs(1,-1);
}

inline void ask(int u,int v){
int ans=0;
if(depth[u]<depth[v]) swap(u,v);
for(int i=TP-1;i>=0;i--){
if(up[u][i]==-1) continue;
if(depth[u]>depth[v]&&depth[up[u][i]]>=depth[v]) ans+=len[u][i],u=up[u][i];
}
/*
//判断同树链
if(u==v){
cout<<ans<<endl;
return;
}
*/
for(int i=TP-1;i>=0;i--){
if(up[u][i]==-1||up[v][i]==-1) continue;
if(up[u][i]!=up[v][i]){
ans+=len[u][i]+len[v][i];
u=up[u][i];
v=up[v][i];
}
}
//这里判u!=v的原因是如果他们如果在同一条树链上
//就不需要往上跳了
//也可以选择在上面判断
if(u!=v){
ans+=len[u][0]+len[v][0];
}
cout<<ans<<endl;
}

int main(){
int cas;
cin>>cas;
while(cas--){
scanf("%d %d",&n,&m);
clearall();
for(int i=1;i<n;i++){
int from,to,cost;
scanf("%d %d %d",&from,&to,&cost);
addedge(from,to,cost);
addedge(to,from,cost);
}
init();
while(m--){
int from,to;
scanf("%d %d",&from,&to);
ask(from,to);
}
}
return 0;
}