• 倍增算法（doubly）

初步学习了一下Lca(最小公共祖先)相关的倍增算法。（又称跳表法）
可以在线求树中两点的最小公共祖先
需要储存信息： 
// lca
//MAXN节点数
int dis[MAXN];//节点到树根距离
//此数组在求两节点距离时使用dis(x,y)=dis[x]+dis[y]-dis[lca]*2
int dep[MAXN];//节点深度
int f[MAXN][22];//节点i向上跳2的j次方到达节点
倍增法与快速取幂思想有些相似，例如求x,y得lca时，
朴素算法：
1，x，y中深度较深的向上走 |dep[x]-dep[y]|
2，x，y一起向上走直到x=y；
倍增算法：
对于每个节点，记录其往上走1个节点，2个节点，4个节点，8个节点，16个节点……2^k个节点所达到的节点编号，具体为利用节点其父亲节点信息，可以通过parent2[v] = parent[parent[v]]得到其向上走两步的节点，再通过这一信息，得到parent4[v]
= parent2[parent2[v]]，即其向上走四步的节点，以此类推......记录节点向上走2^k步的节点为parent[k][v]。有了k = （int）floor（logN / log（2.0））以内的所有信息，就可以二分搜索了。
对于一个节点i，向上跳2^j步，可以拆为i向上跳2^(j-1)步，再向上跳2^(j-1)步（就是4拆成2+2，8拆成4+4，转化为DP求解啦。）
于是：f[u][i]=f[f[u][i-1]][i-1];
板子： 

	//#include <bits/stdc++.h>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
#define pi    acos(-1.0)
#define INF 0x3f3f3f3f3f
#define mod   1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
// lca
//MAXN节点数
int dep[MAXN];//节点深度
int f[MAXN][22];//节点i向上跳2的j次方到达节点
//链式向前星
int n,m,tot;
int head[MAXN];
struct IN
{
    int v;
    int next;
} edge[MAXN<<1];
//树上差分





	void addedge(int u,int v)
{
    edge[tot].v=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}
void build()//建图（原图
{
    tot=1;
    mem(head,0);
    for(int i=1; i<n; i++)
    {
        int u,v;
        s2(u,v);
        addedge(u,v);
        addedge(v,u);
    }
}
void lca_dfs(int u,int pre)
{
    for(int i=1; i<=20; i++)
    {
        f[u][i]=f[f[u][i-1]][i-1];
        if(!f[u][i])
            break;
    }
    for(int i=head[u]; i; i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==pre)
            continue;
        dep[v]=dep[u]+1;
        f[v][0]=u;
        lca_dfs(v,u);
    }
}
void lca_init()
{
    dep[0]=-1;
    dep[1]=1;
    lca_dfs(1,-1);
}
int lca(int x,int y)
{
    if(dep[x]>dep[y])
        swap(x,y);
    for(int i=20; i>=0; i--) //y向上跳
        if(dep[f[y][i]]>=dep[x])
            y=f[y][i];
    for(int i=20; i>=0; i--) //x,y一起向上跳
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    if(x!=y)
        x=f[x][0];
    return x;
}
int main()
{
    while(~s2(n,m))
    {
        build();
        lca_init();
        for(int i=1; i<=m; i++)
        {
            int x,y;s2(x,y);
            printf("%d\n",lca(x,y));
        }
    }
    return 0;
}