CD操作(HDOJ 4547)

2020-05-03 555次阅读 0条评论 4人点赞

五一假期稍微空了一些，总算是有时间做一会儿专题训练了。网络流还没做完，倍增lca就来了，什么时候能肝完呢。。。

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

My Code

倍增LCA+map映射即可，这次尝试了一些骚操作来简化代码。

#include 
#include 
#include 
#include 
using namespace std;
//#define int ll
#define rep(i, a, b) for (signed i = (a); i < (b); ++i)
#define per(i, a, b) for (signed i = (b)-1; i >= (a); --i)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int LOGMAXN = 20;
int t;
int n, m;
map mp; //mp将目录名映射成数字
struct edge
{
	int v;
	int next;
} e[MAXN];
int tot;
int dep[MAXN]; //深度
int head[MAXN];
int p[MAXN][LOGMAXN]; //p[i][j]表示节点i的第2^j的祖先(p[i][0]就是i的第一个祖先，即父亲)
inline void init()	  //初始化清空
{
	mem(e, 0);
	mem(p, 0);
	mem(dep, 0);
	mem(head, 0);
	mp.clear();
	tot = 0;
}
inline void add(int u, int v)
{
	e[++tot].v = v;
	e[tot].next = head[u];
	head[u] = tot;
}
void dfs(int u) //dfs遍历一遍算各点深度
{
	for (int i = head[u]; i; i = e[i].next)
	{
		dep[e[i].v] = dep[u] + 1;
		dfs(e[i].v);
	}
}
int lca(int a, int b) //找最近公共祖先
{
	if (dep[a] < dep[b]) //让a是更远的那个点
		swap(a, b);
	per(i, 0, LOGMAXN) if (dep[a] - (1 << i) >= dep[b]) a = p[a][i]; //先让两者跳到同一深度
	if (a == b)														 //b是a的祖先就直接返回b
		return a;
	per(i, 0, LOGMAXN) if (p[a][i] != p[b][i]) a = p[a][i], b = p[b][i]; //只要没有跳到公共的祖先，就两个点一起往上跳
	return p[a][0];														 //最后最近公共祖先就是他们的父亲
}
signed main()
{
	ios::sync_with_stdio(false); //关同步加速
	cin.tie(0);
	cout.tie(0);

	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		int cnt = 1;
		init();
		rep(i, 1, n)
		{
			string A, B;
			cin >> A >> B;
			if (!mp[A]) //字符串映射到数字
				mp[A] = cnt++;
			if (!mp[B])
				mp[B] = cnt++;
			add(mp[B], mp[A]);	 //建一条父亲指向儿子的边
			p[mp[A]][0] = mp[B]; //记录每个点的父亲是谁
		}
		rep(i, 1, n + 1) if (!p[i][0]) //找根节点，开始遍历求深度
		{
			dfs(i);
			break;
		}
		rep(j, 1, LOGMAXN) rep(i, 1, cnt) p[i][j] = p[p[i][j - 1]][j - 1]; //预处理，计算每个点的第2^j个祖先是谁

		rep(i, 0, m)
		{
			string A, B;
			cin >> A >> B;
			int a = mp[A];
			int b = mp[B];
			int c = lca(a, b);
			int ans = dep[a] - dep[c]; //先一次一次直到到最近公共祖先所在目录
			if (c != b)				   //如果b不是a的祖先，那么就再一次操作从公共祖先c跳到b
				ans++;
			cout << ans << endl;
		}
	}
	return 0;
}