题目链接

题解

思路很粗犷，实现很难受

设\(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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #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<
         
          <<' '; 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 sonvoid 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 fathervoid 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;}