P1122 最大子树和【树形dp】

· · 题解

没有思路没关系，先自己搞一组数据

（随便搞的）

18

-9 -1 -3 -3 2 -8 -3 2 -1 3 3 4 -6 1 2 -1 -9 2

1 2

1 3

2 4

2 5

2 6

3 7

4 8

5 9

5 10

6 11

7 12

7 13

8 14

8 15

11 16

11 17

13 18

（节点编号按bfs序）

从根节点递归

f [ i ] 记录从树梢到i节点的最大美丽值，即

f [ i ] 等于所有所有子树的最大美丽值+自己的美丽值

魅力值是负的节点当然我们不想选了啊

所以如果 f [ i ]是负值，我们就可以直接把他连同子树减掉，也就是赋成0

如上图红色值为每个节点的 f [ i ] = 自己的美丽值 + 所有子节点的红色值

灰色值是负值，减掉后变成 0

最后找到每个节点的红色值 f [ i ]的最大值即为答案

附AC code:

#include<bits/stdc++.h>
using namespace std;
const int N=16010;
int n,m,x,y,f[N],ver[2*N],head[N],tot,ans,next[2*N],w[N];
void add(int x,int y)//加边
{
    ver[++tot]=y;
    next[tot]=head[x];
    head[x]=tot;
}
void dp(int x,int y)
{
    for(int i=head[x];i;i=next[i])
    {
        if(ver[i]==y) continue;//防止重复找边
        dp(ver[i],x);
        f[x]+=f[ver[i]];
    }
    f[x]=max(f[x]+w[x],0);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    for(int i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dp(1,0);
    for(int i=1;i<=n;i++) ans=max(ans,f[i]);
    printf("%d",ans); 
    return 0;
}