hdu 4549 CD操作(lca倍增法)

CD操作
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 325 Accepted Submission(s): 90

Problem Description
　　在Windows下我们可以通过cmd运行DOS的部分功能，其中CD是一条很有意思的命令，通过CD操作，我们可以改变当前目录。
　　这里我们简化一下问题，假设只有一个根目录，CD操作也只有两种方式：
　　
　　1. CD 当前目录名\...\目标目录名 (中间可以包含若干目录，保证目标目录通过绝对路径可达)
　　2. CD .. (返回当前目录的上级目录)
　　
　　现在给出当前目录和一个目标目录，请问最少需要几次CD操作才能将当前目录变成目标目录？

Input
输入数据第一行包含一个整数T(T<=20)，表示样例个数；
每个样例首先一行是两个整数N和M(1<=N,M<=100000)，表示有N个目录和M个询问；
接下来N-1行每行两个目录名A B(目录名是只含有数字或字母，长度小于40的字符串)，表示A的父目录是B。
最后M行每行两个目录名A B，表示询问将当前目录从A变成B最少要多少次CD操作。
数据保证合法，一定存在一个根目录，每个目录都能从根目录访问到。

Output
请输出每次询问的结果，每个查询的输出占一行。

Sample Input
2
3 1
B A
C A
B C

3 2
B A
C B
A C
C A

Sample Output
2
1
2

Source
2013金山西山居创意游戏程序挑战赛——初赛（1）

Recommend
liuyiding
[cpp]
#include<cstdio>
#include<cstring>
#include<map>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define N 100010
#define M 30
int f[N][M],d[N],w;
map<string,int>a;
vector<int>ch[N];
void dfs(int x){//求出所有结点深度
    d[x]=d[f[x][0]]+1;
    //for(int i=1;i<M;i++)f[x][i]=f[f[x][i-1]][i-1];//倍增祖先
    for(int i=ch[x].size()-1;i>=0;i--)
        dfs(ch[x][i]);//遍历儿子
}
int lca(int x,int y){//求x,y最小公共祖先
        if(d[x]<d[y])swap(x,y);//保证x的深度不小于y
    /* for(int k=1,i=M-1;i>=0;i--)
            if((k<<i)<=d[x]-d[y])x=f[x][i];*/
    /*
        int k=d[x]-d[y];
        for(int i=0;i<M;i++)
            if((1<<i)&k)
                x=f[x][i];*/
        for(int i=M-1;i>=0;i--)
            x=d[f[x][i]]>=d[y]?f[x][i]:x;
    if(x==y)return x;//x==y时为最小公共祖先
        for(int i=M-1;i>=0;i--)
            if(f[x][i]!=f[y][i]){
                x=f[x][i];y=f[y][i];
            }
    return f[x][0];
}

int main(){
    int n,m,i,j,T;
    int x,y;
    string A,B;
    scanf("%d",&T);
    while(T--){
        a.clear();
        w=1;
        memset(d,0,sizeof(d));
        memset(f,0,sizeof(f));
        memset(ch,0,sizeof(ch));
        scanf("%d%d",&n,&m);
        for(i=1;i<n;i++){
            cin>>A>>B;
            if((x=a[A])==0)a[A]=x=w++;
            if((y=a[B])==0)a[B]=y=w++;
            ch[y].push_back(x);
            f[x][0]=y;
        }
        for(i=1;i<w;i++)
            if(f[i][0]==0){//找到根遍历
                dfs(i);break;
            }
    for(int i=1;i<M;i++)
        for(x=1;x<=n;x++)
           f[x][i]=f[f[x][i-1]][i-1];//倍增祖先f[i][j]=f[i][j-1]^2
        while(m--){
            cin>>A>>B;
            x=a[A];y=a[B];
            i=lca(x,y);//找到x,y最近公共祖先
            //cout<<x<<" "<<y<<" "<<i<<endl;
            x=d[x]-d[i];
            if(i!=y)x++;
            printf("%d\n",x);
        }
    }
return 0;
}

补充：软件开发 , C++ ,