本文主要是介绍Computer （HDU - 2196，树形 DP - 二次扫描与换根法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一.题目链接：
HDU-2196
二.题目大意：
给一颗无根树，求每个节点所能到达节点的最大距离.
三.分析：
感觉换根好难搞啊，想不清该维护哪些量，额我好笨啊...
附一个大佬讲解，看完就懂了~
还是要多做一些换根dp呀 (ง •̀_•́)ง
四.代码实现：
#include <bits/stdc++.h>
using namespace std;const int M = (int)1e4;
const int inf = 0x3f3f3f3f;int cnt;
int head[M + 5];
struct node
{int v, w, nx;
} Edge[M * 2 + 5];int mx[M + 5], mxi[M + 5];
int sm[M + 5];
int dp[M + 5][2];void init(int n)
{cnt = 0;for(int i = 1; i <= n; ++i){head[i] = -1;mx[i] = sm[i] = -inf;dp[i][0] = dp[i][1] = 0;}
}void add(int u, int v, int w)
{Edge[cnt].v = v;Edge[cnt].w = w;Edge[cnt].nx = head[u];head[u] = cnt++;
}void dfs1(int u, int fa)
{for(int i = head[u]; ~i; i = Edge[i].nx){int v = Edge[i].v;if(v == fa)continue;dfs1(v, u);if(mx[u] <= mx[v] + Edge[i].w){sm[u] = mx[u];mx[u] = mx[v] + Edge[i].w;mxi[u] = v;}else if(sm[u] < mx[v] + Edge[i].w){sm[u] = mx[v] + Edge[i].w;}}if(mx[u] == -inf)mx[u] = 0;
}void dfs2(int u, int fa)
{for(int i = head[u]; ~i; i = Edge[i].nx){int v = Edge[i].v;if(v == fa) continue;dp[v][0] = mx[v];if(mxi[u] == v)dp[v][1] = max(sm[u], dp[u][1]) + Edge[i].w;elsedp[v][1] = max(mx[u], dp[u][1]) + Edge[i].w;dfs2(v, u);}
}int main()
{
// freopen("input.txt", "r", stdin);int n;while(~scanf("%d", &n)){init(n);for(int u = 2, v, w; u <= n; ++u){scanf("%d %d", &v, &w);add(u, v, w);add(v, u, w);}dfs1(1, 0);dp[1][0] = mx[1];dfs2(1, 0);for(int i = 1; i <= n; ++i)printf("%d\n", max(dp[i][0], dp[i][1]));}return 0;
}
这篇关于Computer （HDU - 2196，树形 DP - 二次扫描与换根法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
