首页 > 代码库 > HDOJ 2586 How far away? LCA

HDOJ 2586 How far away? LCA

2024-07-16 14:36:19   219人阅读

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 }

 


联系
我们