hdu 3078 Network RMQ+LCA

题目的意思是给你一个案例，有n个顶点，和q个询问。再下来是n个顶点的权值，再是n-1条边。再下来是q行，当k=0时，就改a顶点的权值为b。

当k>0时，为询问a到b两点距离的第k大的顶点。当两点的距离小于k时，就不会存在第k大的顶点了

很显然是LCA，我以前使用tarjan算法，超时了。后来搜大神的代码，原来用RMQ算法，区间询问最值。

要了解RMQ就http://blog.csdn.net/liang5630/article/details/7917702

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=80008;
int father[N],vis[N],val[N],p[N];
int first[N*2],node[N*2],dep[N*2],dp[N*2][25];
int mi[25];//移位运算
vector<int>map[N];//邻接表

void dfs(int &index,int u,int d,int fa)
{
    index++;//时间搓,全部遍历一次并记录所有节点的父亲，为查找公共祖先做准备
    father[u]=fa;
    node[index]=u;
    dep[index]=d;
    vis[u]=1;
    first[u]=index;
    for(int i=0;i<map[u].size();i++)
    {
        if(!vis[map[u][i]])
        {
            dfs(index,map[u][i],d+1,u);
            index++;
            node[index]=u;
            dep[index]=d;
        }
    }
}
void rmq_init(int n)//RMQ预处理
{
    int i;
     int K = (int)(log((double)n) / log(2.0));
    for(i=1; i<=n; i++) dp[i][0] = i;
    for(int j=1; j<=K; j++)
        for(i=1; i+mi[j]-1 <= n ; i++)
        {
            int a = dp[i][j-1];
            int b = dp[i+mi[j-1]][j-1];
            if(dep[a] < dep[b]) dp[i][j] = a;
            else                dp[i][j] = b;
        }
}
int rmq(int x,int y)
{
    int k=(int)(log((double)(y-x+1))/log(2.0));
    int a=dp[x][k];
    int b=dp[y-mi[k]+1][k];
    if(dep[a]<dep[b])//最近公共祖先的深度
        return a;
    else
        return b;
}
int lca(int a,int b)
{
    int x=first[a];
    int y=first[b];
    int k;
    if(x>y)//可用swap，但是我以前用了超时，所以再也不敢用了。
    {
        k=rmq(y,x);
        return node[k];
    }
    else
    {
        k=rmq(x,y);
        return node[k];
    }
}
int path(int index,int u,int fa)
{
    while(u!=fa )
    {
        p[index++]=val[u];
        u=father[u];
    }
    p[index++]=val[fa];
    return index;
}
bool cmp(int a,int b)
{
    return a>b;
}
void solve(int k,int u,int v)
{
    int l=lca(u,v);
    int tot=0;
    tot=path(tot,u,l);
    tot=path(tot,v,l);
    tot--;
    if(tot<k)
    {
        printf("invalid request!
");
        return ;
    }
    sort(p,p+tot,cmp);
    printf("%d
",p[k-1]);
}

int main()
{
    int n,q,a,b,i;
    scanf("%d%d",&n,&q);
    for(i=0;i<25;i++)
        mi[i]=1<<i;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        map[i].clear();
    }
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        map[a].push_back(b);
        map[b].push_back(a);
    }
    int tot=0;
    memset(vis,0,sizeof(vis));
    dfs(tot,1,1,-1);
    rmq_init(tot);
    for(i=0;i<q;i++)
    {
        int change;
        scanf("%d",&change);
        if(!change)
        {
            scanf("%d%d",&a,&b);
            val[a]=b;
        }
        else
        {
            scanf("%d%d",&a,&b);
            solve(change,a,b);
        }
    }
    return 0;
}