HDU 2196 Computer——树形dp

HDU 2196 Computer——树形dp

需要两遍dfs，一遍向上， 一遍向下

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1e4 + 10;int n, tot, head[maxn], dp[maxn][3];void init() { tot = 0; memset(head, -1, sizeof(head));}struct Edge { int to, cost, next;}edge[maxn*2];void addedge(int u, int v, int cost) { ++tot; edge[tot].to = v, edge[tot].cost = cost, edge[tot].next = head[u]; head[u] = tot;}void dfs1(int u, int p) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v != p) dfs1(v, u); } int pos = -1; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to, cost = edge[i].cost; if (v == p) continue; if (dp[v][0] + cost > dp[u][0]) { dp[u][0] = dp[v][0] + cost; pos = v; } } for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to, cost = edge[i].cost; if (v == p || v == pos) continue; dp[u][1] = max(dp[u][1], dp[v][0] + cost); }}void dfs2(int u, int p) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to, cost = edge[i].cost; if (v == p) continue; dp[v][2] = max(dp[u][2], (dp[v][0] + cost == dp[u][0]) ? dp[u][1] : dp[u][0]) + cost; dfs2(v, u); }}int main() { while (~scanf("%d", &n)) { init(); int v, cost; for (int i = 2; i <= n; i++) { scanf("%d %d", &v, &cost); addedge(i, v, cost); addedge(v, i, cost); } memset(dp, 0, sizeof(dp)); dfs1(1, -1); dfs2(1, -1); for (int i = 1; i <= n; i++) { printf("%d\n", max(dp[i][0], dp[i][2])); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。