倍增LCA

求最近公共祖先：

先用dfs求出各个节点的深度、父节点以及到根节点的距离；
将两个节点中的较深节点的深度调整至于较浅节点相等；
将两个节点的深度同时向上加一至最近公共祖先的子节点；
返回父亲；

倍增法求最近公共祖先：

每个数字都可以分解为若干个二的次方的和（二进制）；
先用dfs求出各个节点的深度、父节点以及到根节点的距离；
将两个节点中的较深节点的深度调整至于较浅节点相等，每次上调i的k次方的深度；
将两个节点的深度同时向上加i的k次方至最近公共祖先的子节点；
返回父亲；

例题：

hdoj 2586 How Far Away题目大意：一个村子里有n个房子，这n个房子用n-1条路连接起来，接下了有m次询问，每次询问两个房子a,b之间的距离是多少。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 using namespace std;
 6 
 7 struct edge{
 8     int to;
 9     int next;
10     int w;
11 };
12 
13 edge e[80008];
14 int p[40004][20]//p[i][j]表示节点i的第2^j次方个祖先
15 ,head[40004],f[40004],dis[40004],deep[40004];
16 int ne=0;
17 int n,m;
18 
19 void add(int a,int b,int c){
20     e[++ne].to=b;e[ne].w=c;e[ne].next=head[a];head[a]=ne;
21 }
22 
23 void dfs(int k,int fa,int dep){
24     int i;
25     f[k]=fa; deep[k]=dep;
26     for(i=head[k];i!=-1;i=e[i].next){
27         int v=e[i].to;
28         if(v!=fa){
29             dis[v]=dis[k]+e[i].w;
30             dfs(v,k,dep+1);
31         }
32     }
33 }
34 
35 void init(){
36     int i,j;
37     for(j=0;(1<<j)<=n;j++)  
38         for(i=1;i<=n;i++)  
39             p[i][j]=-1;//初始化
40     for(i=1;i<=n;i++)p[i][0]=f[i];//每个节点的第一个祖先即自己的父亲
41     for(j=1;(1<<j)<=n;j++)
42         for(i=1;i<=n;i++)
43             if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];//i的第2^j祖先就是i的第2^(j-1)祖先的第2^(j-1)祖先 
44 }
45 
46 int lca(int a,int b){
47     int i,j;
48     if(deep[a]<deep[b])swap(a,b);
49     for(i=0;(1<<i)<=deep[a];i++);
50     i--;
51     for(j=i;j>=0;j--)
52         if(deep[a]-(1<<j)>=deep[b])a=p[a][j];//调整两节点深度至相同
53     if(a==b)return a;
54     for(j=i;j>=0;j--){
55     //倍增法，每次向上进深度2^j，找到最近公共祖先的子结点  
56         if(p[a][j]!=-1&&p[a][j]!=p[b][j]/*防止两节点深度小于最近公共祖先*/){
57             a=p[a][j];
58             b=p[b][j];
59         }
60     }
61     return f[a];
62 }
63 
64 int main(){
65     int i,j,a,b,c,T;
66     scanf("%d",&T);
67     while(T--){
68         memset(head,-1,sizeof(head));
69         scanf("%d%d",&n,&m);
70         for(i=1;i<=n-1;i++){
71             scanf("%d%d%d",&a,&b,&c);
72             add(a,b,c);
73             add(b,a,c);
74         }
75         dis[1]=0;
76         dfs(1,-1,0);//dfs求得每个节点的深度，父节点以及到根节点的距离
77         init();
78         for(i=1;i<=m;i++){
79             scanf("%d%d",&a,&b);
80             printf("%d
",dis[a]+dis[b]-2*dis[lca(a,b)]);//ab间的最短距离是a-->LCA-->b,即dis[a]+dis[b]-2*dis[LCA]
81         }
82     }
83     return 0;
84 }