图论——倍增求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++