倍增（爬树）算法，刚刚学习的算法。对每一个点的父节点，就记录他的2k的父亲。
题目为http://www.luogu.org/problem/show?pid=3379
第一步先记录每一个节点的深度用一个深搜，顺便对每个节点的20赋初值为自己的上一个节点。
第二步通过第一步的初始化对每个节点的2k次进行赋值为fa[i][j]=fa[ fa[i][j-1] ][ j-1 ];自己的j-1次幂的父节点的i-1次就是就是自己的j次幂。
第三步对询问做出处理
1，先判断x，y的深度，如果x比y浅就换位置，让x为深的节点
2，让x上升到和y一样的高度
3，找到他们两个第一个相等的点，一直上升2k次，直到不相等了就让x和y等于他，输出的时候输出的值是fa[x][0]也就是他的上一个点，这是他们相等的点。
输入：N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y，表示x结点和y结点只见有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
输出包含M行，每行包含一个正整数，依次为每一个询问的结果。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define MAX 500010
//=================================================
struct NODE{
int next,point;
NODE(){ next=; }
}edge[];
//=================================================
int N,M,S;
int link[MAX],edgenum=,fa[MAX][];
int deep[MAX];
//=================================================
void init();
void ADD(int ,int );
void DFS(int );
void find();
void pt();
int LCA(int x,int y);
//=================================================
int LCA(int x,int y)
{
if(deep[x]<deep[y])swap(x,y); //如果x比y浅，就让他们两个交换，让x为比较深的那个
for(int i=;i>=;i--){ //注意这里是倒叙，从大k到小k，如果x的k次幂比y深或等于y的深度了就让x等于过去，然后k还会减小
if( deep[ fa[x][i] ] >= deep[y] ) //这样x就可以慢慢逼近直到等于y的深度
x=fa[x][i]; //将x上升到跟y一样的高度上
}
if(x==y)return x;
for(int i=;i>=;i--){ //这里和上边一样，倒叙进行
if( fa[x][i]!=fa[y][i] ) //一只循环到x的0次和y的0次相等的时候，但是这个时候x不等于y也不是公共祖先
x=fa[x][i],y=fa[y][i]; //他们的公共祖先是x的0次幂或y的0次幂所以返回的值是fa[x][0];
}
return fa[x][];
}
//=================================================
void pt()
{
for(int i=;i<=M;i++){
int x,y;
scanf("%d%d*c",&x,&y);
printf("%d\n",LCA(x,y));
}
}
//=================================================
void find()
{
for(int i=;i<=;i++){
for(int j=;j<=N;j++){
fa[j][i]=fa[ fa[j][i-] ][i-]; //确定自己的所有倍增父节点
}
}
}
//=================================================
void DFS(int u)
{
for(int i=link[u];i!=;i=edge[i].next){
int v=edge[i].point;
if(deep[v]==){
deep[v]=deep[u]+; //下一个点的深度为这个点的深度加一
fa[v][]=u; //2的0次幂就是自己的父节点
DFS(v);
}
}
}
//=================================================
void ADD(int x,int y)
{
edgenum++;
edge[edgenum].point=y;
edge[edgenum].next=link[x];
link[x]=edgenum;
}
//=================================================
void init()
{
scanf("%d%d%d",&N,&M,&S);
for(int i=;i<N;i++){
int x,y;
scanf("%d%d*c",&x,&y);
ADD(x,y);
ADD(y,x);
}
}
//=================================================
int main()
{
init(); //初始化
deep[S]=;
DFS(S); //深搜找深度
find(); //找每个点的2k次父节点
pt(); //输入询问输出答案
return ;
}