題目鏈接：

http://acm.hdu.edu.cn/showproblem.php?pid=2586

題意：

無向圖，給定邊及邊權重，任意兩點之間都有一條唯一的道路，道路上每個點只能出現一次。給定詢問，求詢問的結點之間的距離。

分析：

路上每個點只能出現一次~可以轉化成有根樹，問題也即為求最近公共祖先問題~~
這里每條邊加上了距離，求出lca后，用u、v的距離根的距離和減去2倍的根到最近公共祖先的距離即可~

代碼：

#include<cstdio> #include<cstring> #include<vector> using namespace std; #define mem(a, b) memset(a, b, sizeof(a)) #define fuck cout<<"fuck"<<endl; const int maxn = 40005, maxq = 205; typedef pair<int, int>p; vector<p>G[maxn]; #define fi first #define se second int pa[maxn]; bool vis[maxn]; bool in[maxn]; int ance[maxn]; int dist[maxn]; int n, tot; int head[maxn]; int ans[maxn]; struct Query{int to, next, index;}; Query query[maxq * 2]; void add_query(int u, int v, int index) {query[tot].to = v;query[tot].index = index;query[tot].next = head[u];head[u] = tot++;query[tot].to = u;query[tot].index = index;query[tot].next = head[v];head[v] = tot++; } int _find(int x) {if(pa[x] != x) return pa[x] = _find(pa[x]);return x; } void unite(int x, int y) {int rx = _find(x), ry = _find(y);if(rx == ry) return;pa[rx] = ry; } void init() {tot = 0;for(int i = 1; i <= n; i++){G[i].clear();pa[i] = i;}mem(ance, 0);mem(vis, false);mem(head, -1);mem(dist, 0);mem(in, false);mem(ans, 0); } void LCA(int u) {ance[u] = u;vis[u] = true;for(int i = 0; i < G[u].size(); i++){int v = G[u][i].fi;if(vis[v]) continue;dist[v] = dist[u] + G[u][i].se;LCA(v);unite(u, v);ance[_find(u)] = u;}for(int i = head[u]; i != -1; i = query[i].next){int v = query[i].to;if(vis[v]) ans[query[i].index] = dist[u] + dist[v] - 2 * dist[ance[_find(u)]];} } int main(void) {int u, v, k;int a, b, c;int Q;int T;scanf("%d", &T);while(T--){init();scanf("%d%d", &n, &Q);for(int i = 0; i < n - 1; i++){scanf("%d%d%d",&a, &b, &c);G[a].push_back(p(b, c));G[b].push_back(p(a, c));}for(int i = 0; i < Q; i++){scanf("%d%d",&u,&v);add_query(u, v, i);}dist[1] = 0;LCA(1);for(int i = 0; i <Q; i++){printf("%d\n", ans[i]);}}return 0; }

轉載于:https://www.cnblogs.com/Tuesdayzz/p/5758695.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的HDU 2586 How far away ？【LCA】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。