Magic boy Bi Luo with his excited tree

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 559    Accepted Submission(s): 131 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  N  lines , for the i-th line , 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中国大学生程序设计竞赛 - 网络选拔赛   Recommend wange2014   |   We have carefully selected several similar problems for you:   5842  5841  5840  5839  5838    Statistic |  Submit |  Discuss |  Note 题意：给你一棵树，有n个节点n-1条边，边有权值，点也有权值，只要经过边就要付费，走过之前没走过的点拿钱，问从每个点出发最多能得到多少钱。

第一次做树形dp的题就遇到这么恶心的题，赛后看着别人的代码研究了一个下午终于弄出来了，细节不是一般的多，思路要非常非常清晰，不然就gg。下面说下思路：

我们默认1为根节点跑一次dfs，用g数组表示以该节点为根向下走返回到该节点时的最大值,明显有转移方程：g[根] += max(g[子] -边权值*2, 0);从某个点出发获得最大值肯定最后的落点不会在原来的点上，所以我们用dp来存该点最后能获得的最大值和次大值，转移方程详情看代码。最后就知道根节点也就是1的答案就是dp[1][0]。

我们现在只知道1的答案，但是我们不能用一个循环重复上面步骤，时间复杂度很高，所以最后要靠根节点和子节点的关系再跑一次dfs，把其他点的答案全部推出来。子节点最大值的情况只有两种，子节点往上走然后回到原点，再往下走到某个地方达到最大，或者是反过来往下走然后回到原点往上走到最大。往下走到最大就是我们已经记录过的数dp[子][0]，往下走回到原点的最大就是g[子]，往上走我们可以看出根节点和子节点的关系，详情请看代码：

#include<iostream> #include<stack> #include<cstring> #include<map> #include<string> #include<queue> #include<algorithm> #include<cstdio> #include<set> #include<cmath> using namespace std; #define maxn 100005 #define inf 0x3f3f3f3f typedef long long LL; int value[maxn], head[maxn], dp[maxn][2], edge[maxn][3], g[maxn], ans[maxn][3]; struct node{ int u, value, next; }p[maxn << 1]; const int read() { char ch = getchar(); while (ch<'0' || ch>'9') ch = getchar(); int x = ch - '0'; while ((ch = getchar()) >= '0'&&ch <= '9') x = x * 10 + ch - '0'; return x; } void dfs(int x, int fa){ g[x] = value[x]; for (int i = head[x]; i != -1; i = p[i].next){ if (p[i].u == fa) continue; dfs(p[i].u, x); g[x] += max(g[p[i].u] - (p[i].value << 1), 0); } edge[x][0] = edge[x][1] = -1; for (int i = head[x]; i != -1; i = p[i].next){ if (p[i].u == fa || (dp[p[i].u][0] - p[i].value <= 0)) continue; int now = g[x] - max(g[p[i].u] - (p[i].value << 1), 0) + max(dp[p[i].u][0] - p[i].value, 0); if (edge[x][0] == -1){ edge[x][0] = i; dp[x][0] = now; } else if (edge[x][1] == -1 || now > dp[x][1]){ edge[x][1] = i; dp[x][1] = now; if (dp[x][0] < dp[x][1]){ swap(edge[x][0], edge[x][1]); swap(dp[x][0], dp[x][1]); } } } if (edge[x][0] == -1) dp[x][0] = g[x]; if (edge[x][1] == -1) dp[x][1] = g[x]; } void solve(int x,int fa){ for (int i = head[x]; i != -1; i = p[i].next){ if (p[i].u == fa) continue; int y = p[i].u; ans[y][0] = dp[y][0] + max(g[x] - max(g[y] - (p[i].value << 1), 0) - (p[i].value << 1), 0); ans[y][1] = dp[y][1] + max(g[x] - max(g[y] - (p[i].value << 1), 0) - (p[i].value << 1), 0); edge[y][2] = i; if (edge[x][0] == i){ if (g[y] >= (p[i].value << 1)) ans[y][2] = ans[x][1] + p[i].value; else ans[y][2] = g[y] - p[i].value + ans[x][1]; } else{ if (g[y] >= (p[i].value << 1)) ans[y][2] = ans[x][0] + p[i].value; else ans[y][2] = g[y] - p[i].value + ans[x][0]; } if (ans[y][2] > ans[y][1]){ swap(ans[y][2], ans[y][1]); swap(edge[y][2], edge[y][1]); } if (ans[y][1] > ans[y][0]){ swap(ans[y][1], ans[y][0]); swap(edge[y][1], edge[y][0]); } g[y] += max(g[x] - max(g[y] - (p[i].value << 1), 0) - (p[i].value << 1), 0); solve(y, x); } } int main(){ int t; t = read(); for (int tcase = 1; tcase <= t; tcase++){ int n; n = read(); for (int i = 1; i <= n; i++){ value[i] = read(); head[i] = -1; g[i] = 0; } for (int i = 0; i < ((n - 1) << 1); i++){ int x, y, z; x = read(); y = read(); z = read(); p[i].u = y; p[i].value = z; p[i].next = head[x]; head[x] = i++; p[i].u = x; p[i].value = z; p[i].next = head[y]; head[y] = i; } dfs(1, 0); ans[1][0] = dp[1][0]; ans[1][1] = dp[1][1]; solve(1, 0); printf("Case #%d:\n", tcase); for (int i = 1; i <= n; i++){ printf("%d\n", ans[i][0]); } } }