[文章目录]
Description
在Windows下我们可以通过cmd运行DOS的部分功能，其中CD是一条很有意思的命令，通过CD操作，我们可以改变当前目录。
这里我们简化一下问题，假设只有一个根目录，CD操作也只有两种方式：
1. CD 当前目录名...\目标目录名 (中间可以包含若干目录，保证目标目录通过绝对路径可达)
2. CD .. (返回当前目录的上级目录)
现在给出当前目录和一个目标目录，请问最少需要几次CD操作才能将当前目录变成目标目录？
没啥说的。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
#define N 101000
int n,m,t,tot;
string str[2];
char ss[2][55];
map<string , int> v;
bool son[N];
int head[N],to[N],nxt[N],cnt;
int deep[N],fa[N],root;
void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
void dfs(int x)
{
int y,i;
for(i=head[x];i;i=nxt[i])
{
y=to[i];
deep[y]=deep[x]+1;
fa[y]=x;
dfs(y);
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
while(deep[x]>deep[y]) x=fa[x];
if(x==y) return x;
while(x!=y) x=fa[x],y=fa[y];
return x;
}
int query(int x,int y)
{
if(x==y) return 0;
int t=lca(x,y);
if(x==t) return 1;
if(y==t) return deep[x]-deep[t];
return deep[x]-deep[t]+1;
}
void clear()
{
cnt=0,tot=0;
memset(son,0,sizeof(son));
memset(head,0,sizeof(head));
memset(deep,0,sizeof(deep));
memset(fa,0,sizeof(fa));
v.erase(v.begin(),v.end());//map.clear();
}
int main()
{
scanf("%d",&t);
while(t--)
{
clear();
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
scanf("%s%s",ss[0],ss[1]);
str[0]=ss[0];
str[1]=ss[1];
if(v.find(str[0])==v.end())
v[str[0]]=++tot;
if(v.find(str[1])==v.end())
v[str[1]]=++tot;
//printf("%d %d rd\n",v[str[0]],v[str[1]]);
add(v[str[1]],v[str[0]]);
son[v[str[0]]]=1;
}
for(int i=1;i<=n;i++)
if(!son[i]) root=i;
fa[root]=root;
dfs(root);
//for(int i=1;i<=n;i++)
// printf("%d :%d %d\n",i,deep[i],fa[i]);
for(int i=1;i<=m;i++)
{
scanf("%s%s",ss[0],ss[1]);
str[0]=ss[0];
str[1]=ss[1];
//printf("%d %d cd\n",v[str[0]],v[str[1]]);
printf("%d\n",query(v[str[0]],v[str[1]]));
}
}
return 0;
}