题目链接
题解
思路很粗犷，实现很难受
设\(f[i][0|1]\)表示向子树走回来或不回来的最大收益
设\(g[i][0|1]\)表示向父亲走走回来或不回来的最大收益
再设\(h[i]\)为\(f[i][0]\)的次优收益
对于\(f[i][1]\)，贪心选择所有\(f[v][1] - 2 * w \ge 0\)的子树即可
对于\(f[i][0]\)，贪心选择所有没有被选的子树的\(f[v][0] - w \le 0\)的最大值 或者 被选子树\(f[v][1] - 2 * w\)改成\(f[v][0] - w\)后多产生收益的最大值
同时维护次优\(h[v]\)
对于\(g[i][1]\)，设父亲为\(v\)，就等于\(f[v][1] + g[v][1]\)再减去\(i\)对\(f[v][1]\)所作出的贡献【因为往父亲走要忽视\(i\)这课子树】
对于\(g[i][0]\)也是类似的，但是由于忽视\(i\)这课子树后\(f[i][0]\)的决策可能发生改变，所以要在之前算好次优决策\(h[v]\)
这种树形dp简单题都做不出了
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = head[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int head[maxn],ne = 2;
struct EDGE{int to,nxt,w;}ed[maxn << 1];
inline void build(int u,int v,int w){
ed[ne] = (EDGE){v,head[u],w}; head[u] = ne++;
ed[ne] = (EDGE){u,head[v],w}; head[v] = ne++;
}
int n,fa[maxn],d[maxn],w[maxn],f[maxn][2],g[maxn][2],h[maxn],way[maxn];
//cal son
void dfs1(int u){
f[u][0] = f[u][1] = w[u];
int mx = -INF,v,tmp,mx2 = -INF;
Redge(u) if ((to = ed[k].to) != fa[u]){
fa[to] = u; d[to] = ed[k].w; dfs1(to);
if (f[to][1] - 2 * d[to] >= 0){
f[u][1] += f[to][1] - 2 * d[to];
tmp = (f[to][0] - d[to]) - (f[to][1] - 2 * d[to]);
if (tmp > mx) mx2 = mx,mx = tmp,v = to;
else if (tmp > mx2) mx2 = tmp;
}
else if ((tmp = f[to][0] - d[to]) >= 0){
if (tmp > mx) mx2 = mx,mx = tmp,v = to;
else if (tmp > mx2) mx2 = tmp;
}
}
if (mx >= 0) f[u][0] = f[u][1] + mx,way[u] = v;
else f[u][0] = f[u][1],way[u] = 0;
if (mx2 >= 0) h[u] = f[u][1] + mx2;
else h[u] = f[u][1];
}
//cal father
void dfs2(int u){
int v = fa[u];
//back
if (f[u][1] - 2 * d[u] >= 0)
g[u][1] = max(0,f[v][1] + g[v][1] - (f[u][1] - 2 * d[u]) - 2 * d[u]);
else g[u][1] = max(0,f[v][1] + g[v][1] - 2 * d[u]);
//not back
if (f[u][1] - 2 * d[u] >= 0){
g[u][0] = max(0,f[v][1] + g[v][0] - (f[u][1] - 2 * d[u]) - d[u]);
if (way[v] == u)
g[u][0] = max(g[u][0],h[v] + g[v][1] - (f[u][1] - 2 * d[u]) - d[u]);
else g[u][0] = max(g[u][0],f[v][0] + g[v][1] - (f[u][1] - 2 * d[u]) - d[u]);
}
else{
g[u][0] = max(0,f[v][1] + g[v][0] - d[u]);
if (way[v] == u)
g[u][0] = max(g[u][0],h[v] + g[v][1] - d[u]);
else g[u][0] = max(g[u][0],f[v][0] + g[v][1] - d[u]);
}
Redge(u) if ((to = ed[k].to) != fa[u])
dfs2(to);
}
int main(){
int T = read();
REP(C,T){
n = read(); ne = 2;
REP(i,n) w[i] = read(),head[i] = 0;
int a,b,w;
for (int i = 1; i < n; i++){
a = read(); b = read(); w = read();
build(a,b,w);
}
dfs1(1);
dfs2(1);
printf("Case #%d:\n",C);
REP(i,n) printf("%d\n",max(f[i][1] + g[i][0],f[i][0] + g[i][1]));
}
return 0;
}