最近公共祖先(LCA)专题

本文从WordPress迁移而来, 查看全部WordPress迁移文章

LCA的题目是从老博客移过来的,所以代码风格和现在的有些不同。另外LCA的题目并不是太多,选了这几道,算是比较典型的

解决LCA问题,一般用3种方法

  1. 朴素方法:两个点都一直沿路径往上走,直到有某一个节点被经过两次并且是第一次出现这样的点,那么这个就是LCA
    此方法最好理解,但是用得不多,但不代表没作用,有些题目还是需要用到的
  2. LCA转RMQ(在线算法):一般是将LCA转为RMQ问题,用ST算法求解,当然求解RMQ问题有很多方法,不过ST比较常用而已,这样做能及时回答每一个询问
  3. Tarjan算法(离线算法):利用Tarjan算法,不过要先读入所有询问再一并回答,建议认真学习Tarjan算法本质

LCA-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
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
#define N 40010
#define M 35
#define INF 0x3f3f3f3f
#define cl memset

int pos,Pow[M],ver[2*N],R[2*N],first[N],dp[2*N][M];
//数组记得开到2*N,因为遍历后序列长度为2*n-1
int n,tot,head[N];
struct edge
{
int u,v,next;
}e[2*N];
bool vis[N];

void dfs(int u ,int dep){
vis[u] = true; ver[++pos] = u; first[u] = pos; R[pos] = dep;
for(int k=head[u]; k!=-1; k=e[k].next)
if( !vis[e[k].v] ){
int v = e[k].v;
dfs(v,dep+1);
ver[++pos] = u; R[pos] = dep;
}
}

void ST(int len){
int K = (int)(log((double)len) / log(2.0));
for(int i=1; i<=len; i++) dp[i][0] = i;
for(int j=1; j<=K; j++)
for(int i=1; i+Pow[j]-1<=len; i++){
int a = dp[i][j-1] , b = dp[i+Pow[j-1]][j-1];
if(R[a] < R[b]) dp[i][j] = a;
else dp[i][j] = b;
}
}

int RMQ(int x ,int y){
int K = (int)(log((double)(y-x+1)) / log(2.0));
int a = dp[x][K] , b = dp[y-Pow[K]+1][K];
if(R[a] < R[b]) return a;
else return b;
}

int LCA(int u ,int v){
int x = first[u] , y = first[v];
if(x > y) swap(x,y);
int res = RMQ(x,y);
return ver[res];
}

/******* main *******/
for(int i=0; i<M; i++) Pow[i] = (1<<i);
scanf("%d%d",&n,&q);
tot = 0;
cl(head,-1,sizeof(head));
cl(vis,false,sizeof(vis));
for(int i=1; i<n; i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
pos = 0;
dfs(1,1);
ST(2*n-1);
while(q--){
int u,v;
scanf("%d%d",&u,&v);
int lca = LCA(u,v);
printf("lca = %d\n",lca);
}

LCA-Tarjan离线算法模板

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
int tot,head[N],__head[N];
struct edge{
int u,v,w,next;
}e[2*N];
struct ask{
int u,v,lca,next;
}ea[M];
int fa[N];

inline void add_edge(int u,int v,int w){
e[tot].u = u; e[tot].v = v; e[tot].w = w;
e[tot].next = head[u]; head[u] = tot++;
}

inline void add_ask(int u ,int v){
ea[tot].u = u; ea[tot].v = v; ea[tot].lca = -1;
ea[tot].next = __head[u]; __head[u] = tot++;
}

int Find(int x){
return x == fa[x] ? x : fa[x] = Find(fa[x]);
}

void Tarjan(int u){
vis[u] = true;
for(int k=head[u]; k!=-1; k=e[k].next)
if( !vis[e[k].v] ){
int v = e[k].v , w = e[k].w;
Tarjan(v);
fa[v] = u;
}
for(int k=__head[u]; k!=-1; k=ea[k].next)
if( vis[ea[k].v] ){
int v = ea[k].v;
ea[k].lca = ea[k^1].lca = Find(v);
}
}

/********** main ***********/
scanf("%d%d",&n,&q);
cl(head,-1,sizeof(head));
cl(__head,-1,sizeof(__head));
tot = 0;
for(int i=1; i<n; i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,w);
}
tot = 0;
for(int i=0; i<q; i++){
int u,v;
scanf("%d%d",&u,&v);
add_ask(u,v);
add_ask(v,u);
}
for(int i = 1; i <= n; i++){
fa[i] = i; vis[i] = false;
}
Tarjan(1);
for(int i=0; i<q; i++){
int s = i * 2 , u = ea[s].u , v = ea[s].v , lca = ea[s].lca;
printf("lca = %d\n",lca);
}

具体问题具体分析,但是可以使用Tarjan算法的时候推荐使用Tarjan算法。代码量少速度快,另外Tarjan算法容易产生变形,值得深究

  • hdu 2586 How far away ?

    模板题,直接求LCA,可以在线,离线算法均可解,可以测试一下模板

  • poj 1986 Distance Queries

    模板题,直接求LCA

  • hdu 2874 Connections between cities

    模板题,不过不是树是森林,所以某些点不存在LCA,要做判断

  • zoj 3195 Design the city

    任然算是模板题,上面的题要求两点间的最短距离,这里要求3点间的最短距离,其实就是两两之间求一次LCA并计算出距离,然后相加除以2即可

  • hdu 3078 Network

    LCA + 修改点权值 + 排序:每个点有初始的权值,一边查询一边伴随着修改某些点的权值,查询是从a到b路径中第k大的权值是多少。不需要太多的技巧,修改操作就直接修改,查询操作先求LCA,然后从a走到b保存下所有的权值,排序,然后直接输出即可

  • poj 2763 Housewife Wind

    LCA + 修改边权:一边查询两点间的距离,一边修改某些边权。对于修改了某些边的边权,就要从此开始遍历下面的子孙后代更改他们的dir值(点到根的距离)。也不需要太多技巧,直接按题意实现即可,不过时间比较糟糕,用线段树或树状数组可以对修改操作进行优化,时间提升很多

  • poj 3694 Network

    连通分量 + LCA : 先缩点,再求LCA,并且不断更新,这题用了朴素方法来找LCA,并且在路径上做了一些操作

  • poj 3417 Network

    LCA + Tree DP : 在运行Tarjan处理完所有的LCA询问后,进行一次树DP,树DP不难,但是要想到用树DP并和这题结合还是有点难度

  • poj 3728 The merchant

    LCA + 并查集的变形,优化:好题,难题,思维和代码实现都很有难度,需要很好地理解Tarjan算法中并查集的本质然后灵活变形,需要记录很多信息(有点dp的感觉)

  • hdu 3830 Checkers

    LCA + 二分:好题,有一定思维难度。先建立出二叉树模型,然后将要查询的两个点调整到深度一致,然后二分LCA所在的深度,然后检验

  • poj 2793 Cactus

    判断无向图的仙人掌图(Cactus),做法是LCA + Tree DP