学步园

RMQ

int euler[MAXN*2];
int dep[MAXN*2];
int pos[MAXN];
int top;
int rmq[MAXN*2][16];


void dfs(int u,int depth,int fa)
{
	euler[++top]=u;
	dep[top]=depth;
	pos[u]=top;
	INE(i,u,e)
	{
	    int v=e[i].v;
	    if(v==fa) continue;
	    dfs(v,depth+1,u);
	    euler[++top]=u;
	    dep[top]=depth;
	}
}
void RMQinit()
{
	rep(i,1,top) rmq[i][0]=i;
	rep(j,1,16)
	rep(i,1,top) if(i+(1<<j)-1<=top)
	{
	    if(dep[rmq[i][j-1]]<dep[rmq[i+(1<<j-1)][j-1]])
	        rmq[i][j]=rmq[i][j-1];
	    else
	        rmq[i][j]=rmq[i+(1<<j-1)][j-1];
	}
}
int RMQ(int l,int r)
{
    int len=r-l+1;
    int LOG=0;
    for(;1<<LOG+1<=len;LOG++);
    if(dep[rmq[l][LOG]]<dep[rmq[r-(1<<LOG)+1][LOG]])
        return rmq[l][LOG];
    else
        return rmq[r-(1<<LOG)+1][LOG];
}
void LCAinit()
{
    dfs(1,0,-1);
    RMQinit();
}
int LCA(int u,int v)
{
    if(pos[u]>pos[v]) swap(u,v);
    return euler[RMQ(pos[u],pos[v])];
}

倍增

http://blog.csdn.net/willinglive/article/details/40023375