首页 > 代码库 > HDOJ 2586 How far away? LCA
HDOJ 2586 How far away? LCA
http://acm.hdu.edu.cn/showproblem.php?pid=2586
题意:
给一棵树,多次查询点到点距离。
分析:
d[x][y] = d[x][root] + d[y][root] - 2 * d[lca(x,y)][root],所以求lca即可。因为tarjan是在dfs的过程中求lca,顺便就把点到根的距离也求了。
敲了代码才发现,讲解的伪代码都是先递归子节点,染色,再回答询问的顺序,但是平时写的时候一般是建了双向边,先递归子节点再染色会导致环的情况从而死循环。所以网上的题解大多是先染色,再查询,再递归子节点。不过我试了一下,至少这一题,先染色,然后先回答询问或是先递归子节点都是可以AC的。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 using namespace std; 6 7 typedef pair<int, int> P; 8 const int maxn = 40100; 9 10 int T, n, m, x, y, z;11 int f[maxn], d[maxn], ans[300];12 bool vis[maxn];13 vector<P> e[maxn], q[maxn];14 15 int getf(int x)16 {17 if (f[x] == x) return x;18 return f[x] = getf(f[x]);19 }20 void unionxy(int x, int y)21 {22 int xroot = getf(x), yroot = getf(y);23 f[yroot] = xroot;24 }25 void tarjan(int x)26 {27 f[x] = x;28 vis[x] = true;29 for (int i = 0; i < q[x].size(); i++){30 int v = q[x][i].first, id = q[x][i].second;31 if (vis[v]){32 int lca = f[getf(v)];33 ans[id] = d[x] + d[v] - 2 * d[lca];34 }35 }36 for (int i = 0; i < e[x].size(); i++){37 int v = e[x][i].first, w = e[x][i].second;38 if (!vis[v]){39 d[v] = d[x] + w;40 tarjan(v);41 unionxy(x, v);42 f[getf(x)] = x;43 }44 }45 }46 int main()47 {48 scanf("%d", &T);49 while(T--)50 {51 scanf("%d %d", &n, &m);52 for (int i = 0; i <= n; i++){53 q[i].clear(); e[i].clear();54 }55 for (int i = 1; i < n; i++){56 scanf("%d%d%d", &x, &y, &z);57 e[x].push_back(make_pair(y, z));58 e[y].push_back(make_pair(x, z));59 }60 for (int i = 0; i < m; i++){61 scanf("%d %d", &x, &y);62 if (x == y) ans[i] = 0;63 else{64 q[x].push_back(make_pair(y, i));65 q[y].push_back(make_pair(x, i));66 }67 }68 memset(vis, 0, sizeof(vis));69 d[1] = 0;70 tarjan(1);71 for (int i = 0; i < m; i++)72 printf("%d\n", ans[i]);73 }74 return 0;75 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。