首先，如果要求的是以1作为开始位置的话，很容易想到一个dp[u][2]，其中dp[u][0]表示以u节点为开始位子的子树最后回到u节点获得最大值，dp[u][1]表示不回来。转移就显而易见了。
然后，考虑如果u节点结果已经计算出，怎么计算他的儿子节点v的答案。
那么，也容易想到转移ans[v]=max(dp[v][1], dp2[u][!v][0] + dp[v][1] - 2 * c, dp2[u][!v][1] + dp[v][0] - c)， 其中dp2[u][!v][0]表示以u为根节点，不遍历以v且回到u的最大值，dp2[u][!v][1] 表示以u为根节点，不遍历以v且不回到u的最大值。其中dp2可以在dp计算出来后，动态的维护一下。
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<cmath> #include<bitset> #include<queue> #include<stack> #include<set> #include<map> #define xx first #define yy second #define LL long long #define MP make_pair #define INF 0x3f3f3f3f #define CLR(a, b) memset(a, b, sizeof(a)) #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 using namespace std; const int maxn = 100100; LL dp[maxn][2], ans[maxn]; vector<pair<int, int> > G[maxn]; int val[maxn]; void dfs(int u, int fa) { dp[u][0] = val[u]; dp[u][1] = 0; for(int i = 0; i < G[u].size(); i ++) { int v = G[u][i].first, c = G[u][i].second; if(v == fa) continue; dfs(v, u); if(dp[v][0] > c * 2) { dp[u][0] += dp[v][0] - c * 2; dp[u][1] = max(dp[v][1] - dp[v][0] + c, dp[u][1]); } else dp[u][1] = max(dp[v][1] - c, dp[u][1]); } dp[u][1] = dp[u][0] + dp[u][1]; } void dfs2(int u, int fa, LL dp0, LL dp1) { LL mx = 0, mx2 = 0, all = val[u]; for(int i = 0; i < G[u].size(); i ++) { int v = G[u][i].first, c = G[u][i].second; if(v == fa) { if(dp0 - 2 * c > 0) { all += dp0 - 2 * c; if(dp1 - dp0 + c >= mx) mx2 = mx, mx = dp1 - dp0 + c; else if(dp1 - dp0 + c > mx2) mx2 = dp1 - dp0 + c; } else { if(dp1 - c >= mx) mx2 = mx, mx = dp1 - c; else if(dp1 - c > mx2) mx2 = dp1 - c; } } else { if(dp[v][0] - 2 * c > 0) { all += dp[v][0] - 2 * c; if(dp[v][1] - dp[v][0] + c >= mx) mx2 = mx, mx = dp[v][1] - dp[v][0] + c; else if(dp[v][1] - dp[v][0] + c > mx2) mx2 = dp[v][1] - dp[v][0] + c; } else { if(dp[v][1] - c >= mx) mx2 = mx, mx = dp[v][1] - c; else if(dp[v][1] - c > mx2) mx2 = dp[v][1] - c; } } } for(int i = 0; i < G[u].size(); i ++) { int v = G[u][i].first, c = G[u][i].second; if(v == fa) continue; LL add = all, tmp = dp[v][1] - c; if(dp[v][0] - 2 * c > 0) { add -= (dp[v][0] - 2 * c); tmp = dp[v][1] - dp[v][0] + c; } ans[v] = add + dp[v][1] - 2 * c; ans[v] = max(ans[v], dp[v][1]); if(tmp == mx) { ans[v] = max(ans[v], add + mx2 + dp[v][0] - c); dfs2(v, u, add, add + mx2); } else { ans[v] = max(ans[v], add + mx + dp[v][0] - c); dfs2(v, u, add, add + mx); } } } int main() { int T, cas = 1, n; scanf("%d", &T); while(T --) { scanf("%d", &n); for(int i = 1; i <= n; i ++) { scanf("%d", &val[i]); G[i].clear(); } for(int i = 1; i < n; i ++) { int u, v, c; scanf("%d%d%d", &u, &v, &c); G[u].push_back(MP(v, c)); G[v].push_back(MP(u, c)); } dfs(1, -1); ans[1] = dp[1][1]; dfs2(1, -1, 0, 0); printf("Case #%d:\n", cas ++); for(int i = 1; i <= n; i ++) printf("%I64d\n", ans[i]); } return 0; }