本文共 2167 字，大约阅读时间需要 7 分钟。
题意：根目录能一次到达其任意子目录，子目录返回上一层目录需要一次，给出目录关系，问从某个目录到某个目录最少要多少步。
操作数 ，就是起点到最近公共祖先的距离。
然后讨论下，如果最近公共祖先等于终点，那么答案就是起点到祖先的高度差 ，否则就是高度差加一 。
#include #include #include #include #include #include using namespace std;const int maxn = 111111;int father[maxn];map , int> ans;vector q[maxn];int getfather(int x){ if (father[x] != x) return father[x] = getfather(father[x]); return father[x];}int len, head[maxn];int l[maxn], r[maxn];struct Node{ int to; int next;}e[maxn * 2];int deep[maxn];int color[maxn];void add(int from, int to){ e[len].to = to; e[len].next = head[from]; head[from] = len++;}int un(int x, int y){ int fx = getfather(x); int fy = getfather(y); father[fy] = fx;}void dfs(int x){ for (int i = head[x]; i != -1; i = e[i].next){ int cc = e[i].to; dfs(cc); un(x, cc); } color[x] = 1; for (int i = 0; i < q[x].size(); i++){ int t = q[x][i]; if (color[t]){ int gg = getfather(t); ans[make_pair(x, t)] = gg; ans[make_pair(t, x)] = gg; } }}void build(int root, int dep){ deep[root] = dep; for (int i = head[root]; i != -1; i = e[i].next){ int cc = e[i].to; build(cc, dep + 1); }}int gg[maxn];void init(int n){ len = 0; memset(head, -1, sizeof(head)); memset(color, 0, sizeof(color)); memset(gg, 0, sizeof(gg)); for (int i = 1; i <= n; i++) father[i] = i; for (int i = 1; i <= n; i++) q[i].clear();}int main(){ int T; int n, M; char a[100], b[100]; cin >> T; map m; while (T--){ int cnt = 1; m.clear(); scanf("%d%d", &n, &M); init(n); for (int i = 0; i < n - 1; i++){ scanf("%s%s", a, b); int c; int d; if (!m[a]) m[a] = cnt++; if (!m[b]) m[b] = cnt++; c = m[a]; d = m[b]; add(d, c); gg[c] = 1; } int root; for (int i = 1; i <= n; i++) if (!gg[i]){ root = i; break; } build(root, 1); for (int i = 0; i < M; i++){ scanf("%s%s", a, b); int c = m[a]; int d = m[b]; l[i] = c; r[i] = d; q[c].push_back(d); q[d].push_back(c); } dfs(root); for (int i = 0; i < M; i++){ int t = ans[make_pair(l[i], r[i])]; if (t == r[i]){ printf("%d\n", deep[l[i]] - deep[t]); } else{ printf("%d\n", deep[l[i]] - deep[t] + 1); } } } return 0;}
转载于:https://www.cnblogs.com/yigexigua/p/4083540.html