思路：先選定1為樹根，進(jìn)行第一次深搜，很容易求出節(jié)點u到其子節(jié)點的最長距離和次長距離，求次長距離的目的是如果u的跟節(jié)點最長路徑經(jīng)過u則dp的時候就不能取其跟節(jié)點的最長距離，應(yīng)該取其次長距離;然后進(jìn)行第二次深搜，搜索節(jié)點u經(jīng)過其跟節(jié)點的最長距離。如果令dp[u][0],dp[u][1],分別為節(jié)點u到子節(jié)點的最長，次長距離，dp[u][2]表示節(jié)點u經(jīng)過其跟節(jié)點v的最長距離，則狀態(tài)方程為 dp[u][2] = max(dp[v][2],dp[u][0] + edge[j].w == dp[v][0] ? dp[v][1] : dp[v][0]) + edge[j].w;最后輸出答案為max(dp[u][0],dp[u][2]),即某點u的最長距離為其到子節(jié)點的最長距離和經(jīng)過其跟節(jié)點的最長距離二者之中的最大者。

#include<iostream> #include<cstdio> #include<cstring> #define MAX 11111 using namespace std; typedef long long int LL; typedef struct{int to, next, w; }Node; Node edge[MAX]; LL head[MAX], dp[MAX][3]; void AddEdge(int u, int v, int w, int i){edge[i].to = v;edge[i].w = w;edge[i].next = head[u];head[u] = i; } void dfs_to_son(int i){LL bigest = 0, biger = 0;for(int j = head[i];j != -1;j = edge[j].next){int v = edge[j].to;dfs_to_son(v);LL temp = dp[v][0] + edge[j].w;if(bigest <= temp){biger = bigest;bigest = temp;}else if(temp > biger) biger = temp;}dp[i][0] = bigest;dp[i][1] = biger; } void dfs_to_father(int i){for(int j = head[i];j != -1;j = edge[j].next){int v = edge[j].to;dp[v][2] = max(dp[i][2], dp[v][0] + edge[j].w == dp[i][0] ? dp[i][1]:dp[i][0]) + edge[j].w;dfs_to_father(v);} } int main(){int n, u, w;/* freopen("in.c", "r", stdin); */while(~scanf("%d", &n)){memset(dp, 0, sizeof(dp));memset(head, -1, sizeof(head));for(int i = 2;i <= n;i ++){scanf("%d%d", &u, &w);AddEdge(u, i, w, i-1);}dfs_to_son(1);dfs_to_father(1);for(int i = 1;i <= n;i ++) printf("%lld\n", max(dp[i][2], dp[i][0]));}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/wangzhili/p/3950278.html

總結(jié)

以上是生活随笔為你收集整理的HDOJ 2196的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。