題目鏈接：點擊查看

題目分析：給出n個節點組成的一棵樹，每條邊都有一個權值w，現在給出m個詢問，每次詢問需要回答點x到點y之間的距離之和

題目分析：因為看到了兩點之間的距離之和，一開始是想直接上樹鏈剖分，然后線段樹維護的，但轉念一想，其實可以直接用一個樹上前綴和來維護的，dfs的時候順便把前綴和維護一下，sum[v]=sum[u]+w，表示的是節點v到根節點的前綴和，雖然題目給出的是一個無根樹，但是我們可以隨便設置一個節點當做根節點，不會影響到最終答案的

維護完前綴和后對于兩個點跑一下lca然后直接求答案就好了，因為權值是在邊上，所以直接sum[x]+sum[y]-2*sum[lca]就好了

這個題目的數據我一開始是有點怕爆int，因為2*1.6*1e9已經爆掉int了，所以我把上面的式子稍微換了一下順序，就不用擔心了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=4e4+100;struct Node {int to,w;Node(int TO,int W){to=TO;w=W;} };vector<Node>node[N];int n,m,limit;int sum[N];int deep[N],dp[N][20];void dfs(int u,int f,int dep) {deep[u]=dep;dp[u][0]=f;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(auto i:node[u]){int v=i.to;int w=i.w;if(v==f)continue;sum[v]=sum[u]+w;dfs(v,u,dep+1);} }int LCA(int x,int y) {if(deep[x]<deep[y])swap(x,y);for(int i=limit;i>=0;i--)if(deep[x]-deep[y]>=(1<<i))x=dp[x][i];if(x==y)return x;for(int i=limit;i>=0;i--)if(dp[x][i]!=dp[y][i]){x=dp[x][i];y=dp[y][i];}return dp[x][0]; }void init() {sum[1]=0;for(int i=1;i<=n;i++)node[i].clear();limit=log2(n)+1; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%d%d",&n,&m);init();for(int i=1;i<n;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);node[x].push_back(Node(y,w));node[y].push_back(Node(x,w));}dfs(1,0,0);while(m--){int x,y;scanf("%d%d",&x,&y);int lca=LCA(x,y);printf("%d\n",sum[x]-sum[lca]+sum[y]-sum[lca]);}}return 0; }

?

總結

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

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