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;
}
