圖論——倍增求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++