本文主要是介绍hdu 4547 CD操作（金山居 LCA算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
LCA算法：首先用CD ..回退到公共最近最现，再一次性到达目的地。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;const int maxn = 100006;
int dp[maxn][20], father[maxn], dep[maxn];
bool vis[maxn], mark[maxn];
int n;map<string, int> hash;
void getDepth(int u) { //从叶节点向根求结点深度int v = u, l = 0;while (dep[v] < 0) {v = father[v];l++;}while (v != u) {dep[u] = l + dep[v];u = father[u];l--;}
}
//模版
void DP() {int i, j;memset (dp, -1, sizeof (dp));for (i = 1; i <= n; i++)dp[i][0] = father[i];for (j = 1; (1<<j) <= n; j++)for (i = 1; i <= n; i++)//if (dp[i][j-1] != -1)dp[i][j] = dp[dp[i][j-1]][j-1];
}int get_nearest_ancestor(int u, int v) {int tmp, log, i;if (dep[u] < dep[v]) {tmp = u; u = v; v = tmp;}for (log = 1; (1<<log) <= dep[u]; log++);log--;for (i = log; i >= 0; i--)if (dep[u]-(1<<i) >= dep[v])u = dp[u][i];if (u == v) return u;for (i = log; i >= 0; i--)if (dp[u][i] != -1 && dp[u][i] != dp[v][i])u = dp[u][i],v = dp[v][i];return father[u];
}int main()
{int t, i, x, y;string A, B;int m, a, b, total;cin >> t;while(t--) {hash.clear();memset(vis, false, sizeof (vis));memset(mark, false, sizeof (mark));memset(dep, -1, sizeof (dep));cin >> n >> m;total = 0;for (i = 1; i < n; i++) {cin >> A >> B;if(hash.find(A) == hash.end())a = hash[A] = ++total;elsea = hash[A];if(hash.find(B) == hash.end())b = hash[B] = ++total;else b = hash[B];father[a] = b;vis[a] = mark[b] = true;}for (i = 1; i <= n; i++)if (!vis[i]) break;father[i] = i;dep[i] = 0;for (i = 1; i <= n; i++) //遍历所有叶节点求结点的深度if (!mark[i])getDepth(i);DP();while(m--){cin >> A >> B;x = hash[A], y = hash[B];int fa = get_nearest_ancestor(x, y);int ans = dep[x] - dep[fa];if(fa != y) ++ans;cout << ans << endl;}}return 0;
}这篇关于hdu 4547 CD操作（金山居 LCA算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
