題意：給一棵樹，詢問u和v之間的邊權和。

解題思路：找到u和v的最近公共祖先，它們之間的距離為dis[u]+dis[v]-2*dis[lca(u,v)]

#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std;const int maxn = 40005; struct Edge {int k,next,cost; }edge[maxn<<1]; struct Ask {int k,next,id; }ask[maxn<<1]; int n,m,cnt1,cnt2,pre[maxn],head[maxn]; int dis[maxn],fa[maxn]; int ans[maxn],color[maxn]; bool vis[maxn];void addedge(int u,int v,int c) {edge[cnt1].k = v;edge[cnt1].cost = c;edge[cnt1].next = pre[u];pre[u] = cnt1++; }void addask(int u,int v,int id) {ask[cnt2].k = v;ask[cnt2].next = head[u];ask[cnt2].id = id;head[u] = cnt2++; }int find(int x) {if(fa[x] == x) return x;return fa[x] = find(fa[x]); }void Tarjan(int u,int len) {vis[u] = true;fa[u] = u;dis[u] = len;for(int i = pre[u]; i != -1; i = edge[i].next){int v = edge[i].k;if(vis[v]) continue;Tarjan(v,len + edge[i].cost);fa[v] = u;}color[u] = 1;for(int i = head[u]; i != -1; i = ask[i].next){int v = ask[i].k;if(color[v]){int ancestor = find(v);ans[ask[i].id] = dis[u] + dis[v] - 2*dis[ancestor];}} }int main() {int t,u,v,c;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);memset(pre,-1,sizeof(pre));memset(head,-1,sizeof(head));cnt1 = cnt2 = 0;for(int i = 1; i < n; i++){scanf("%d%d%d",&u,&v,&c);addedge(u,v,c);addedge(v,u,c);}for(int i = 1; i <= m; i++){scanf("%d%d",&u,&v);addask(u,v,i);addask(v,u,i);}memset(vis,false,sizeof(vis));Tarjan(1,0);for(int i = 1; i <= m; i++)printf("%d\n",ans[i]);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 2586(LCA + 节点间距离)的全部內容，希望文章能夠幫你解決所遇到的問題。

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