CD操作
倍增法 https://i.cnblogs.com/EditPosts.aspx?postid=8605845
Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 4 Accepted Submission(s) : 3
Problem Description
在Windows下我们可以通过cmd运行DOS的部分功能，其中CD是一条很有意思的命令，通过CD操作，我们可以改变当前目录。
这里我们简化一下问题，假设只有一个根目录，CD操作也只有两种方式：
1.
CD 当前目录名\...\目标目录名 (中间可以包含若干目录，保证目标目录通过绝对路径可达)
2. 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操作。数据保证合法，一定存在一个根目录，每个目录都能从根目录访问到。
B(目录名是只含有数字或字母，长度小于40的字符串)，表示A的父目录是B。最后M行每行两个目录名A
B，表示询问将当前目录从A变成B最少要多少次CD操作。数据保证合法，一定存在一个根目录，每个目录都能从根目录访问到。
Output
请输出每次询问的结果，每个查询的输出占一行。
Sample Input
2
3 1
B A
C A
B C
3 1
B A
C A
B C
3 2
B A
C B
A C
C A
Sample Output
2
1
2
1
2
- 从父目录到任意一个子目录的距离都是1
- 用一个flag记录一下询问是从左到右还是从右到左，有几种情况
- 左边是右边的父亲，距离为1
- 右边是左边的父亲，距离是dis[v]到lca(u,v)
- 其他情况+1
其他就是离线求Tarjan的lca了
#include<iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=+;
const int M=*N;
int pre[N],first[N],first2[N],tot,tot2;
bool vis[N];//标记有没有询问
int n;
int fa[N],ans[N],cnt;
int vis2[N],dis[N];
map<string,int>m; struct edge
{
int v,next;
} e[M];
struct Query
{
int v,next,id,flag;//flag用来标记是从左到右还是从到左
} query[M]; void add(int u,int v)
{
e[tot].v=v;
e[tot].next =first[u];
first[u]=tot++;
}
void dfs(int u,int len)//建立深度
{
vis2[u]=;
dis[u]=len;
for(int i=first[u];~i;i=e[i].next)
{
int v=e[i].v;
if(!vis2[v])
dfs(v,len+);
}
} void add_query(int u,int v,int id,int flag)//建立询问的边
{
query[tot2].flag =flag;
query[tot2].id=id;
query[tot2].v=v;
query[tot2].next=first2[u];
first2[u]=tot2++;
} int find(int x)
{
return x==pre[x]?x:pre[x]=find(pre[x]);
} void lca(int u,int fa)//Targin算法
{
for(int i=first[u];~i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
lca(v,u);
pre[v]=u;
}
vis[u]=;
for(int i=first2[u];~i;i=query[i].next)
{
int v=query[i].v;
if(vis[v])//那么find(v)就是最近公共祖先
{
int id=query[i].id;
int flag=query[i].flag ;
if(flag==)
{
if(u==find(v))
{
ans[id]=;//直接跃上找到父目录
}
else if(find(u)==v)
ans[id]=dis[u]-dis[find(v)];//向下走找到目标目录
else
ans[id]=dis[u]-dis[find(v)]+;//一个越到父目录，再向下找
}
else//
{
int u1=v;
int v1=u;
if(u1==find(v1))
ans[id]=;
else if(find(u1)==v1)
ans[id]=dis[u1]-dis[find(v)];
else
ans[id]=dis[u1]-dis[find(v)]+;
}
}
}
} void init()
{
mem(first,-);
mem(first2,-);
mem(vis,);
mem(vis2,);
mem(fa,-);
mem(ans,);
tot=;
tot2=;
cnt=;
m.clear();
for(int i=; i<=n; i++)
pre[i]=i;
} struct node
{
int u,v;
} zz[N]; int main()
{
int t,mm;
string s1,s2;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&mm);
init();
for(int i=; i<n; i++)
{
cin>>s1>>s2;
if(!m[s1]) m[s1]=cnt++;
if(!m[s2]) m[s2]=cnt++;
int a=m[s1],b=m[s2];
add(a,b);
add(b,a);
fa[a]=b;
}
int root=;
while(~fa[root]) root=fa[root];
dfs(root,);
for(int i=; i<=mm; i++)
{
cin>>s1>>s2;
int a=m[s1],b=m[s2];
zz[i].u=a,zz[i].v=b;
add_query(a,b,i,);
add_query(b,a,i,);
}
lca(root,root);
for(int i=; i<=mm; i++)
{
int u=zz[i].u,v=zz[i].v;
if(u==v)
puts("");
else
printf("%d\n",ans[i]);
}
}
return ;
}
Source
2013金山西山居创意游戏程序挑战赛——初赛（1）