题意：问从每个节点出发，能获得的最大价值。
做法：树形DP。
思路：用两个DFS。
第一个DFS维护出，每个节点，从它的所有子节点返回该点能得到的最大价值（subtree_max_back）,它的一个子节点不返回该点可以得到的最大价值（subtree_max_nback）和次大值（subtree_submax_nback）,以及不返回的最大价值是当那个点不返回时得到的（subtree_max_nback_id）。
第二个DFS，找出答案。
一个点的答案来至于，所有子节点返回该节点+ 父亲节点不返回该节点 或者 有个子节点不返回该节点+从父亲节点返回该节点。
代码为：
#include<stdio.h> #include<string.h> #include<math.h> #include<queue> #include<vector> #include<iostream> #include<complex> #include<string> #include<set> #include<map> #include<algorithm> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define nn 100100 #define ll long long #define ULL unsiged long long #define pb push_back #define mod 1000000007 #define inf oxfffffffffff #define eps 0.00000001 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 int val[nn],head[nn],sz; struct Edge { int to, next, len; Edge(){} Edge(int to, int next, int len) :to(to), next(next), len(len) {} }edge[nn * 2]; void add_edge(int x, int y, int z) { edge[sz] = Edge(y, head[x], z); head[x] = sz++; } int subtree_max_back[nn], subtree_max_nback[nn];//从所有子树中返回最大值/有一个子节点不返回的最大值 int subtree_submax_nback[nn], subtree_max_nback_id[nn];//有一个子节点不返回的次大值，最大不反回值来至与那个子节点不返回 int ans[nn];//记录答案 void dfs1(int u, int fa) { subtree_max_back[u] = val[u]; subtree_max_nback[u] = val[u]; subtree_submax_nback[u] = 0;//初始化，一个节点的最大返回/不返回的最大值为其本身，次大值为0 for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa) continue; dfs1(v, u); } for (int i = head[u]; i != -1; i = edge[i].next)//得到每个节点的子节点返回该点的可获得最大价值 { int v = edge[i].to; if (v == fa) continue; int l = edge[i].len; subtree_max_back[u] += max(0, subtree_max_back[v] - 2 * l); } for (int i = head[u]; i != -1; i = edge[i].next)//更新有个子节点不返回该点的最大值和次大值 { int v = edge[i].to; if (v == fa) continue; int l = edge[i].len; int val = subtree_max_back[u] - max(0, subtree_max_back[v] - 2 * l) + max(0, subtree_max_nback[v] - l); //子节点v不返回时，该节点可得到的最大价值 if (val >= subtree_max_nback[u])//更新最大 { subtree_submax_nback[u] = subtree_max_nback[u]; subtree_max_nback[u] = val; subtree_max_nback_id[u] = v; } else if (val > subtree_submax_nback[u])//更新次大 subtree_submax_nback[u] = val; } } void dfs2(int u, int fa, int fa_back, int fa_nback) { ans[u] = max(subtree_max_back[u] + fa_nback, subtree_max_nback[u] + fa_back); //该点的最优答案来至于，所有子节点返回该节点+ 父亲节点不返回该节点/有个子节点不返回该节点+从父亲节点返回该节点 for (int i = head[u]; i != -1; i = edge[i].next) // 更新他的儿子节点v { int v = edge[i].to; if (v == fa) continue; int l = edge[i].len; int fa, fnb; fa = fa_back + subtree_max_back[u] - max(0, subtree_max_back[v] - 2 * l); //除去v节点，返回该点的最大值 if (v == subtree_max_nback_id[u])//如果该子节点是该点不返回的最优答案时的不返回节点，用次优值取更新该节点 { fnb = max(fa_nback + subtree_max_back[u] - max(0, subtree_max_back[v] - 2 * l), fa_back + subtree_submax_nback[u] - max(0, subtree_max_back[v] - 2 * l)); // 从不返回的点的来源来更新该点，（该子节点的父亲节点的父亲节点/该子节点的父亲节点的其他子节点） } else//不是得到最优不返回值得子节点的更新 { fnb = max(fa_nback + subtree_max_back[u] - max(0, subtree_max_back[v] - 2 * l), fa_back + subtree_max_nback[u] - max(0, subtree_max_back[v] - 2 * l)); } dfs2(v, u, max(0, fa-2*l), max(0, fnb-l)); } } int main() { int t, kcase = 1; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); sz = 0; memset(head, -1, sizeof(head)); for (int i = 1; i <= n; i++) scanf("%d", &val[i]); for (int i = 1; i < n; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add_edge(x, y, z); add_edge(y, x, z); } dfs1(1, 0); dfs2(1, 1, 0, 0); printf("Case #%d:\n", kcase++); for (int i = 1; i <= n; i++) printf("%d\n", ans[i]); } return 0; }
