图论——倍增求LCA

LCA,最近公共祖先。

这是在树上的算法,但是为什么我们把它归为图论呢?

因为它对图论太重要了,其实,树也是图,是任意二节点只有一条路径的图。

我们来看一下LCA的栗子:

这就是LCA,很好理解吧!

那问题来了,怎么实现求两点的LCA呢?

 

其实很简单,用暴力法就可以了。先用树的DFS遍历求出树的深度,在一个一个向父节点搜索,找到一样的就是它们的LCA了!

简单粗暴吧!

 

大家可能会感到疑惑,真的有这么简单?

是的,是这么简单。来回顾一下问题:怎么实现求两点的LCA,DFS是能求,也好求。但是有一个缺点:太慢。

当我们的树的深度很大时,我们无法承受这巨大的复杂度,所以我们要想办法优化它。

 

我们先来看一下暴力解法的代码,并确保你理解了。

code

 1 #include <bits/stdc++.h>
 2 #define MAXN 100005
 3 using namespace std;
 4 typedef long long ll;
 5 int v[MAXN];//标记节点是否被访问
 6 int fa[MAXN];//每个节点的父亲节点
 7 int depth[MAXN];//每个节点的深度
 8 vector<int>g[MAXN];//vector存树 
 9 void init()//初始化 
10 {
11     memset(v,0,sizeof(v));
12     memset(depth,0,sizeof(depth));
13     memset(fa,0,sizeof(fa));
14     for(int i=0;i<MAXN;i++)
15     {
16         g[i].clear();
17     }
18 }
19 void dfs(int s,int step)//DFS遍历 
20 {
21     depth[s]=step;
22     v[s]=1;
23     for(int i=0;i<g[s].size(); i++)
24     {
25         int k=g[s][i];
26         if(!v[k])
27         {
28             dfs(k,step+1);
29         }
30     }
31 }
32 int lca(int u,int v)
33 {
34     int fatheru=u;
35     int fatherv=v;
36     int depthu=depth[fatheru];
37     int depthv=depth[fatherv];
38     while(depthu<depthv)
39     {
40         fatherv=fa[fatherv];
41         depthv=depth[fatherv];
42     }
43     while(depthu>depthv)
44     {
45         fatheru=fa[fatheru];
46         depthu=depth[fatheru];
47     }
48     while(fatherv!=fatheru)
49     {
50         fatherv=fa[fatherv];
51         fatheru=fa[fatheru];
52     }
53     return fatherv;//暴力求LCA 
54 }
55 int main()
56 {
57     int n,m;
58     init();
59     cin>>n;
60     for(int i=1; i<n; i++)
61     {
62         int x,y;
63         cin>>x>>y;
64         g[x].push_back(y);
65         fa[y]=x;
66     }
67     int root=0;
68     for(int i=1;i<=n;i++)
69     {
70         if(fa[i]==0)
71             root = i;
72     }
73     dfs(root,1);
74     int u,v;
75     cin>>u>>v;
76     cout<<lca(u,v)<<endl;
77     return 0;
78 }

额,有些长。

我们来讲讲如何~~优化~~

刚才,我们讲到,当树的深度太大时,复杂度很高,为什么呢?

因为每次跳一步太慢,若我们一次能往上走多步的话,时间复杂度会得到有效的控制。

 

这样的方法,我们叫树上倍增法。

 

这是一个运用广泛的算法,不仅仅用于求LCA..

我们用二维数组 f[ i ] [ k ]表示i的2^k倍祖先,就是i向上走2^k步到达的点,若它爆了深度,也就是它只向的节点不存在,就返回0.

f[ i ][ 0 ]表示 i 的 father 

对于任意的 i 属于 [ 1 ,  log n ],f [ i ][ k ]=f [ f[ x ][ k - 1] ][ k - 1 ];

这就是神奇的状态转移方程  ~QAQ~

 

蒟蒻:怎么涉及了DP?

 

是的,是涉及了DP,这也是它的难点之一。

 

 下面是代码:

 1 const int SIZE=50010;
 2 int f[SIZE][20],d[SIZE],dist[SIZE];
 3 int ver[2*SIZE],Next[2*SIZE],edge[2*SIZE],head[SIZE];
 4 //采用图存储
 5 int T,n,m,tot=0,t;
 6 queue<int>q;
 7 void add(int x,int y,int z)
 8 {
 9     ver[++tot]=y;edge[tot]=z;Next[tot]=head[x];head[x]=tot;
10 }
11 void bfs()        //预处理 
12 {
13     q.push(1);
14     d[1]=1;
15     while(q.size())
16     {
17         int x=q.front();q.pop();
18         for(int i=head[x];i;i=Next[i])
19         {
20             int y=ver[i];
21             if(d[y])
22                 continue;
23             d[y]=d[x]+1;
24             dist[y]=dist[x]+edge[i];
25             f[y][0]=x;
26             for(int j=1;j<=t;j++)
27                 f[y][j]=f[f[y][j-1]][j-1];
28             q.push(y);
29         }
30     }
31 }
32 int lca(int x,int y)
33 {
34     if(d[x]>d[y])
35         swap(x,y);
36     for(int i=t;i>=0;i--)
37     {
38         if(d[f[i][i]]>=d[x])
39             y=f[y][i];
40     }
41     if(x==y)
42         return x;
43     for(int i=t;i>=0;i--)
44     {
45         if(f[x][i]!=f[y][i])
46         {
47             x=f[x][i];
48             y=f[y][i];
49         }
50     }
51     return f[x][0];
52 }

可以看出,代码还是很长,这也是LCA让我们恼火的一点,记模板会很困难。还是理解了他们更好。

上面的代码用了图的链式前向星存法。

树也是一种图,所以这样保存是合理的。

bfs函数是预处理出每个节点的深度,在进行LCA算法。

 

明天就NOIP了,祝大家NOIP2018 rp++  

关键词:int lca 我们 size fatherv fa depth for fatheru 节点

相关推荐:

关于主席树的入门,讲解和题单

【算法总结】树相关

BZOJ 3489 A simple rmq problem 可持久化KDtree/二维线段树

分块入门

Bzoj2534:后缀自动机 主席树启发式合并

线段树专题训练

北京集训:20180325

专题训练之最大流

c语言spline

北京集训:20180311