倍增LCA模闆

原帖在這：http://blog.csdn.net/crazy_ac/article/details/7796497

LCA可以離線tarjan去求，也可以線上倍增去求。

記二維數組p[u][i]表示u的2^i個祖先是誰，i==0就是父節點。那麼可以通過 p[u][i]=p[p[u][i-1]][i-1]來遞推出所有的情況，然後再求lca（x,y）的時候，根據x,y的深度，先将深度大的點通過p[][放縮到與x相同的深度，做法是用二進制表示出深度差，然後從低到高掃描，若第i位為1，那麼b=p[b][i]，否則不變即第i位為1時，b跳轉到其2^i個祖先處，看起來有點抽象，不過畫個圖或者單步監視一下就明白了。放縮到統一深度後，直接枚舉一下答案就出來了...

這裡放一個poj1330的模闆，題意就是給一個數，然後給一個查詢求LCA。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int POW = 16;
const int maxn=10000;
vector<int> edge[maxn];
int p[maxn][16];
int d[maxn];
int n,m,k;
void dfs(int u,int fa){
    d[u]=d[fa]+1;
    p[u][0]=fa;
    for(int i=1;i<POW;i++) p[u][i]=p[p[u][i-1]][i-1];
    int sz=edge[u].size();
    for(int i=0;i<sz;i++){
        int v=edge[u][i];
        if(v==fa) continue;
        dfs(v,u);
    }
}
int lca( int a, int b ){
    if( d[a] > d[b] ) a ^= b, b ^= a, a ^= b;
    if( d[a] < d[b] ){
        int del = d[b] - d[a];
        for( int i = 0; i < POW; i++ ) if(del&(1<<i)) b=p[b][i];
    }
    if( a != b ){
        for( int i = POW-1; i >= 0; i-- )
            if( p[a][i] != p[b][i] )
                 a = p[a][i] , b = p[b][i];
        a = p[a][0], b = p[b][0];
    }
    return a;
}
int ideg[maxn];
int main()
{
//    freopen("in.txt","r",stdin);
    int tt;
    scanf("%d",&tt);
    while (tt--)
    {
        memset(d,0,sizeof d);
        memset(p,0,sizeof p);
        memset(ideg,0,sizeof ideg);
        int x,y;
        scanf("%d",&n);
        for (int i=1; i<=n; i++)
        edge[i].clear();
        for (int i=1; i<n; i++)
        {
            scanf("%d%d",&x,&y);
            ideg[y]++;
            edge[x].push_back(y);
            edge[y].push_back(x);
        }
        int root;
        for (int i=1; i<=n; i++)
        if (ideg[i]==0) root=i;
        dfs(root,-1);
        scanf("%d%d",&x,&y);
        cout<<lca(x,y)<<endl;
    }
    return 0;
}