題意:
? ? ? 給你一棵樹,求出每一個點到其他點的最大距離.

思路:

? ? ? 每個點的最大距離只有兩種情況,1是自己忘下面走的最大,二是網上走的最大,取他們的最大便是答案,每個點網下面的最大可以空過dfs直接在回溯的時候求出來,但網上走的呢?往上走其實就是他父親往上走的最大 和 他父親往下走最大 中大的那個加上他和她父親的距離得到的,但是他父親往下走的最大有可能是他這條路,就是路過他,那么怎么辦呢,我們可以再第一遍dfs求最大的時候求出個次大,第二大,當最大的路路過他時那么直接用次大的代替最大,就這樣樹形dp一邊,得到自己網上走的最大,然后輸出自己網上走最大和往下走最大中的最優值就行了,具體看代碼就懂了,第一遍深搜從下網上,第二遍從上往下...據說還可以用樹的直徑的性質做,求出樹的直徑,然后輸出max(dis[s] ,dis[t]);自己沒試驗行不行,不知道時間能不能超時,如果超時我感覺可以用LCA去優化...

#include<stdio.h> #include<string.h>#define N 11000 typedef struct {int to ,next ,cost; }STAR;STAR E[N];int list[N] ,tot; int maxz[N] ,maxc[N]; int dp[N] ,mer[N];void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }int maxx(int a ,int b) { return a > b ? a : b; }void DFS1(int s) {int maz = 0 ,mac = 0 ,mk = 0;for(int k = list[s] ;k ;k = E[k].next){int to = E[k].to;mk = 1;DFS1(to);if(maz < maxz[to] + E[k].cost){ mer[s] = to;mac = maz;maz = maxz[to] + E[k].cost;} elsemac = maxx(mac ,maxz[to] + E[k].cost);}if(mk){maxz[s] = maz;maxc[s] = mac;}else maxz[s] = maxc[s] = 0; }void DFS2(int s) {for(int k = list[s] ;k ; k = E[k].next){int to = E[k].to;if(to == mer[s])dp[to] = maxx(dp[s] ,maxc[s]) + E[k].cost;elsedp[to] = maxx(dp[s] ,maxz[s]) + E[k].cost;DFS2(to);} }int main () {int n ,i ,a ,b;while(~scanf("%d" ,&n)){memset(list ,0 ,sizeof(list));tot = 1;for(i = 2 ;i <= n ;i ++){scanf("%d %d" ,&a ,&b);add(a ,i ,b);}DFS1(1);dp[1] = 0;DFS2(1);for(i = 1 ;i <= n ;i ++)printf("%d\n" ,maxx(maxz[i] ,dp[i]));}return 0; }

總結

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

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