求LCA最近公共祖先的在线倍增算法模板

求LCA最近公共祖先的在线倍增算法模板_C++

　　倍增求 LCA 是在线的，而且比 ST 好写多了，理解起来比 ST 和 Tarjan 都容易，于是就自行脑补吧，代码写得容易看懂

　　关键理解 f[i][j] 表示 i 号节点的第 2^j 个父亲，也就是往上走 2^j个节点

　　求 LCA 的时候先倍增让两点深度一样，再倍增求

　　另外丢两个链接，这两个有详细讲解

　　　　ST 算法 http://www.cnblogs.com/hadilo/p/5837517.html

　　　　Tarajan 算法 http://www.cnblogs.com/hadilo/p/5840390.html

　　可能代码缩进不是很好看，因为我的 Emacs 用的默认缩进

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 const int N=100001,L=20;
10 int m,first[N],next[N],d[N],f[N][L];
11 inline void dfs(int x,int dep)
12 {
13   d[x]=dep;
14   m=max(m,dep);
15   for (int i=first[x];i;i=next[i]) dfs(i,dep+1);
16 }
17 int log2(int x)
18 {
19   int k=0;
20   while (x>1)
21     {
22       x>>=1;
23       k++;
24     }
25   return k;
26 }
27 int main()
28 {
29   int i,j,n,s,x,y,root;
30   scanf("%d",&n);
31   for (i=1;i<=n;i++)
32     {
33       scanf("%d",&f[i][0]);
34       if (!f[i][0]) root=i;
35       next[i]=first[f[i][0]];
36       first[f[i][0]]=i;
37     }
38   dfs(root,0);
39   s=log2(m);
40   for (j=1;j<=s;j++)
41     for (i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
42   scanf("%d",&n);
43   while (n--)
44     {
45       scanf("%d%d",&x,&y);
46       if (d[x]<d[y]) swap(x,y);
47       s=log2(d[x]-d[y]);
48       while (d[x]>d[y])
49     {
50       if (d[x]-(1<<s)>=d[y]) x=f[x][s];
51       s--;
52     }
53       s=log2(d[x]);
54       while (s>-1)
55     {
56       if (f[x][s]!=f[y][s])
57         {
58           x=f[x][s];
59           y=f[y][s];
60         }
61       s--;
62     }
63       printf("%d
",x==y?x:f[x][0]);
64     }
65   return 0;
66 }