【HDOJ 5834】Magic boy Bi Luo with his excited tree（树型DP）

Magic boy Bi Luo with his excited tree

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Problem Description Bi Luo is a magic boy, he also has a migic tree, the tree has N nodes , in each node , there is a treasure, it’s value is V[i], and for each edge, there is a cost C[i], which means every time you pass the edge i , you need to pay C[i]. You may attention that every V[i] can be taken only once, but for some C[i] , you may cost severial times. Now, Bi Luo define ans[i] as the most value can Bi Luo gets if Bi Luo starts at node i. Bi Luo is also an excited boy, now he wants to know every ans[i], can you help him?   Input First line is a positive integer T(T≤104) , represents there are T test cases.Four each test：The first line contain an integer N(N≤105). The next line contains N integers V[i], which means the treasure’s value of node i(1≤V[i]≤104) . For the next N - 1 lines, each contains three integers u , v , c , which means node u and node v are connected by an edge, it’s cost is c(1≤c≤104) . You can assume that the sum of N will not exceed 106 .   Output For the i-th test case , first output Case #i: in a single line , then output ans[i] in a single line.   Sample Input 1 5 4 1 7 7 7 1 2 6 1 3 1 2 4 8 3 5 2   Sample Output Case #1: 15 10 14 9 15   Author UESTC   Source 2016中国大学生程序设计竞赛 - 网络选拔赛

题目大意： 一棵树，节点有价值，树边有花费。 节点价值只能get到一次，树边花费每次经过都要消耗。 输出从节点1~n出发，分别能得到的最大净价值(节点收获-树边花费)

一眼树型dp

可能是做树dp做多了有感觉了，或者是因为训练计划上类似的题较多，。

首先考虑子问题： 节点1做根，输出最大价值。 令 dp[u][0] 表示从u出发，往下遍历，返回u的最大价值。 dp[u][1] 表示从u出发，往下遍历，不回u的最大价值。 这样转移其实就是 dp[u][1]=max(dp[u][0]+dp[v][1]+wuv,dp[v][0]+dp[u][1]+2⋅wuv) dp[u][0]=∑dp[v][0]+2⋅wuv

回到此题，需要求得其实是以1 ~ n为根的最大价值。 那么第一遍dfs求出上面的数组。 第二遍dfs当从u遍历v时，给v传递两个参数： 从u出发，不经过v，回到u的最大价值 从u出发，不经过v，不回u的最大价值

这样当遍历v时，考虑与 dp[v][0] 还有 dp[v][1] 组合一下，去个最大即可。 求不经过v回到u的最大价值好办，第一遍dfs的时候对路标记一下，如果经过了v，去掉v这条路上获得的最大价值即可。 但是求不经过v，不回到u的最大价值时，如果 dp[u][1] 经过v了，单单除去v这条路，又变成了回到u的最大价值。 因此考虑给dp再加一个记录，对于u而言，第一遍dfs找到回到u的最大价值和不会到u的最大以及次大价值。

代码如下：

#include <bits/stdc++.h> using namespace std; const int mxn = 112345; struct Edge { int v,w,next,f; }; Edge eg[mxn*2]; int head[mxn],val[mxn]; int ans[mxn]; int dp[mxn][3],nxt[mxn][3],tp; void Add(int u,int v,int w) { eg[tp].v = v; eg[tp].w = w; eg[tp].next = head[u]; eg[tp].f = 0; head[u] = tp++; } void dfs1(int u,int pre) { dp[u][0] = dp[u][1] = dp[u][2] = val[u]; nxt[u][0] = nxt[u][1] = nxt[u][2] = -1; int v,w; for(int i = head[u]; i != -1; i = eg[i].next) { v = eg[i].v; if(v == pre) continue; w = eg[i].w; dfs1(v,u); dp[u][1] += max(0,dp[v][0]-2*w); dp[u][2] += max(0,dp[v][0]-2*w); if(w <= dp[v][1]) { int tmp = dp[u][0]+dp[v][1]-w; if(tmp > dp[u][1]) { if(dp[u][1] > dp[u][2]) { dp[u][2] = dp[u][1]; nxt[u][2] = nxt[u][1]; } dp[u][1] = tmp; nxt[u][1] = i; } else if(tmp > dp[u][2]) { dp[u][2] = tmp; nxt[u][2] = i; } } if(w*2 <= dp[v][0]) { eg[i].f = 1; dp[u][0] += dp[v][0]-w*2; } } } void dfs2(int u,int pre,int bk,int nbk) { bk = max(bk,0); nbk = max(nbk,0); //printf("u = %d bk = %d nbk = %d\n",u,bk,nbk); int v,w; ans[u] = max(dp[u][0]+nbk,dp[u][1]+bk); int nbk1,nbk2,bbk; for(int i = head[u]; i != -1; i = eg[i].next) { v = eg[i].v; w = eg[i].w; if(v == pre) continue; bbk = dp[u][0]; nbk1 = dp[u][1]; nbk2 = dp[u][2]; if(eg[i].f) { bbk = bbk-dp[v][0]+w*2; nbk1 = nbk1-dp[v][0]+2*w; nbk2 = nbk2-dp[v][0]+2*w; } if(nxt[u][1] == i) { nbk1 = dp[u][1]-dp[v][1]+w; } if(nxt[u][2] == i) { nbk2 = dp[u][2]-dp[v][1]+w; } dfs2(v,u,bbk-2*w+bk,max(bbk+nbk-w,bk+max(nbk1,nbk2)-w)); } } int main() { int t,u,v,w,n; scanf("%d",&t); for(int z = 1; z <= t; ++z) { printf("Case #%d:\n",z); memset(head,-1,sizeof(head)); tp = 0; scanf("%d",&n); for(int i = 1; i <= n; ++i) scanf("%d",&val[i]); for(int i = 1; i < n; ++i) { scanf("%d%d%d",&u,&v,&w); Add(u,v,w); Add(v,u,w); } dfs1(1,1); dfs2(1,1,0,0); for(int i = 1; i <= n; ++i) { // printf("%d:\n",i); // printf("back:%d\n",dp[i][0]); // printf("nbk1:%d %d\n",nxt[i][1] == -1? -1: eg[nxt[i][1]].v,dp[i][1]); // printf("nbk2:%d %d\n",nxt[i][2] == -1? -1: eg[nxt[i][2]].v,dp[i][2]); printf("%d\n",ans[i]); } } return 0; }