題目鏈接：點擊查看

題目大意：給定n個點以及n-1條邊，保證可以組成一棵樹，問每個點所能到達的最遠距離

題目分析：首先這是一顆無向圖所組成的樹，經過分析，我們可以得到任何一個點，對于它所能到達的最遠距離取決于兩個條件，一個是該點向下可以到達的最遠距離，或者是該點向上可以到達的最遠距離，求該點向下的距離好求，可以利用樹形dp的一般形式，回溯法，直接自底向上地往上求，不僅需要維護一個最大值，還需要維護一個次大值，接下來會用到，然后就是怎么求向上可以達到的距離了，我們可以在寫一個dfs，剛才那個是自底向上維護，那么新的dfs就變成自頂向下維護就好了，其實本質上就是交換了一下轉移方程和遞歸入口的順序。

那么接下來在分析一下轉移方程該怎么寫，剛才我們提到了一共需要維護三個值，即向下的最大值，向下的次大值和向上的最大值，故我們需要用三個數組來維護，我們就用dp[N][3]來維護，第一維分別表示每個點，第二維的0,1,2分別表示以上三個值。

關于最大值和次大值，只需要遵循

更新最大值前先更新次大值

更新不了最大值時檢查是否可以更新次大值

這樣就可以直接自底向上轉移了，還剩一個向上的最大值，這個我們該怎么想呢

我先將轉移方程放上然后在來解釋：

dp[v][2]=max(dp[v][0]+w==dp[u][0]?dp[u][1]:dp[u][0],dp[u][2])+w;

其中v表示為u的兒子，w表示為u和v之間的權值

既然是自頂向下轉移，那么轉移的方向就是u->v來轉移，dp[u][2]可以當做已知條件來用，我們可以直接用這個值加上u和v之間的權值w來更新dp[v][2]，這樣確實是其中的一種情況，但卻不一定是最優解，所以我們需要經過比較選擇出最優解來更新dp[v][2]才行，那么還有哪些途徑可以更新它呢？我們假設當前的u為根節點，那么既然v位于u的子樹中，我們需要判斷v是否位于u向下最大值的子樹中，如果是的話，那么經過v點向上，我們可以經過根節點u當做中轉點，到達u點的另一個次大值的子樹中，這樣可以保證了距離最大，如果v不在u的向下最大值的子樹中，那么必定可以經過u到達最大值的子樹中，這樣通過比較這三種情況來確定了更新dp[v][2]的狀態。

最后輸出的結果便是從dp[i][0]和dp[i][2]中選擇較大的一個輸出了。

上代碼

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+100;struct Node {int to,w;Node(int TO,int W){to=TO;w=W;} };vector<Node>node[N];int dp[N][3];//0：向下最大值，1：向下次大值，2：向上最大值void dfs_down(int u,int fa) {int mmax=0;//最大值int mx=0;//次大值for(int i=0;i<node[u].size();i++){int v=node[u][i].to;int w=node[u][i].w;if(v==fa)continue;dfs_down(v,u);int temp=dp[v][0]+w;if(temp>=mmax){mx=mmax;mmax=temp;}else if(temp>mx){mx=temp;}}dp[u][0]=mmax;dp[u][1]=mx; }void dfs_up(int u,int fa) {for(int i=0;i<node[u].size();i++){int v=node[u][i].to;int w=node[u][i].w;if(v==fa)continue;dp[v][2]=max(dp[v][0]+w==dp[u][0]?dp[u][1]:dp[u][0],dp[u][2])+w;dfs_up(v,u);} }int main() { // freopen("input.txt","r",stdin);int n;while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)node[i].clear();for(int i=2;i<=n;i++){int w,u;scanf("%d%d",&u,&w);node[u].push_back(Node(i,w));node[i].push_back(Node(u,w));}memset(dp,0,sizeof(dp));dfs_down(1,-1);dfs_up(1,-1);for(int i=1;i<=n;i++)cout<<max(dp[i][0],dp[i][2])<<endl;}return 0; }

?

?

總結

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

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