題目鏈接：點擊查看

題目大意：給出一個n個節點的樹，我們需要選出一個節點，到其余任何節點的距離和最小

題目分析：這個題我的第一反應是用樹的重心，先求出來符合條件的點，然后再跑一遍dfs求距離，最后輸出就好，因為樹的重心的定義是子樹節點<= n/2, 而每一棵樹的重心不會超過2個，所以記錄答案的時候也變得簡單了許多，去網上查了一下沒查到用樹的重心做的題解，還以為是自己思路想錯了，但是自己寫寫試試之后果不其然的過了，和預想的一樣（yeah！！）然后還有一個方法，是先跑一邊dfs求出子樹的節點數，以及子樹到根節點的距離和，在跑一邊dfs求出除了子樹外的點到根節點的距離和，先求出最小的距離和，然后遍歷一遍n個頂點，找到符合條件的點輸出答案即可。

上述方法中涉及到了幾個變量的維護都需要用樹形dp來維護，我來稍微解釋一下其轉移方程吧

首先是維護子樹節點，這個最簡單，只需要自底向上，根節點依次累加子節點的答案即可。

其次是關于樹的重心的方法中，已知符合條件的點，再維護距離，這個需要在累加子節點答案的基礎上，每次最后再加一遍該節點的子樹上的節點數量，因為求得是距離和，之前累加子節點的答案求出來的是子樹上的點到子節點的距離和，而它們到達根節點還差一個單位的距離，每個點都差一個單位的距離，總共就差了該根節點子樹上的點的個數的距離了。

然后就是關于第二個方法了，第二個方法中需要維護三個數組，一個是剛才提到的子樹節點數量，這里用num數組記錄，還有一個是維護子樹中節點到根節點的距離和，這里用dp[i][0]數組維護，這兩個數組上述已經解釋過了，下面解釋一下最后一個不太好理解的，dp[i][1]，表示除了子樹外的點到根節點的距離和。其實說是不好理解只是因為有點抽象，我先把公式放出，先不化簡，然后具體解釋具體意義，應該就不難理解了：

dp[v][1]=(n-num[v])+(dp[u][1])+(dp[u][0]-(dp[v][0]+num[v]));

依次轉換成偽代碼，就變成了：（以下使用“其他的點”來代替“除了子樹節點外的點”，并且“該點”以及“父節點”指的都是“當前節點”和“當前節點的父節點”）

其他的點到達該點的距離和=（其他的點的數量）+（其他的點到父節點的距離和）+（父節點的子樹到父節點的距離和-（包含該點在內的子樹到父節點的距離））

可能這幾行文字能把人繞暈。。因為實在是太抽象了，如果實在想不過來，可以自己畫個圖，就一目了然了，本質就是一個區間分成了的各個部分。

直接上代碼了：

樹的重心：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e4+100; int n,I,R;int num[N];vector<int>node[N];int ans,mark1,mark2;LL dp[N];//記錄距離和 void dfs(int u,int fa) {int mmax=-1;num[u]=1;for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==fa)continue;dfs(v,u);mmax=max(mmax,num[v]);num[u]+=num[v];}mmax=max(mmax,n-num[u]);if(ans>mmax){ans=mmax;mark1=u;mark2=-1;}else if(ans==mmax)mark2=u; }void dfs2(int u,int fa) {num[u]=1;for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==fa)continue;dfs2(v,u);num[u]+=num[v];dp[u]+=dp[v]; }dp[u]+=num[u]-1; }int main() { // freopen("input.txt","r",stdin)int w;cin>>w;while(w--){scanf("%d%d%d",&n,&I,&R);for(int i=1;i<=n;i++)node[i].clear();for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}memset(dp,0,sizeof(dp));mark1=mark2=-1;ans=inf;dfs(1,-1);dfs2(mark1,-1);cout<<dp[mark1]*I*I*R<<endl;if(mark2!=-1){cout<<min(mark1,mark2)<<' '<<max(mark1,mark2)<<endl;}else{cout<<mark1<<endl;}cout<<endl;}return 0; }

傳統做法：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e4+100; int n,I,R;int num[N];LL ans;vector<int>node[N];LL dp[N][2];//記錄距離：dp[i][0]表示該節點的子樹到該點的距離和，dp[i][1]表示除了該節點子樹外的點到該點的距離和void dfs(int u,int fa) {num[u]=1;for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==fa)continue;dfs(v,u);num[u]+=num[v];dp[u][0]+=dp[v][0];}dp[u][0]+=num[u]-1; }void dfs2(int u,int fa) {for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==fa)continue;dp[v][1]=dp[u][1]+n-num[v]+dp[u][0]-dp[v][0]-num[v];dfs2(v,u);}ans=min(ans,dp[u][1]+dp[u][0]); }int main() { // freopen("input.txt","r",stdin)int w;cin>>w;while(w--){scanf("%d%d%d",&n,&I,&R);for(int i=1;i<=n;i++)node[i].clear();for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}memset(dp,0,sizeof(dp));dfs(1,-1);ans=inf;dfs2(1,-1);bool first=true;cout<<ans*I*I*R<<endl;for(int i=1;i<=n;i++){if(dp[i][0]+dp[i][1]==ans){if(first)first=false;elsecout<<' ';cout<<i;}}cout<<endl<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 4045 Power Station(树形dp/树的重心)的全部內容，希望文章能夠幫你解決所遇到的問題。

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