题解 P1122 【最大子树和】

traceson · 2016-10-13 11:05:03 · 题解

这题咋一看还真有点树形DP的意思，也不管是不是树形了，反正是个DP。

思路也和大多一样，找出“根”，（因为这道题的特殊性，我们不需要找根，只用随便找个点当做根就行了，因为它是一棵树）然后递归找出其子数，判断其子树的价值是否为正，为正值就加上。并且在我们找的过程中每次找完一棵字数时的值就用一个全局变量answer记录一下当前值取个max，这样最后answer的值就是最后答案。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int ans;
int f[16010];
struct node{
    int to,next;
}e[32010];//这里用一个结构体记录每条边得终点和其相邻的边
int head[16010];
int k=0;
void build(int u,int to)//建树（邻接表操作）
{
    e[++k].to=to;
    e[k].next=head[u];
    head[u]=k;
}
int dfs(int x,int fa)//因为是双向边所以传一个当前点的父亲，避免重复走回来
{
    int sum=f[x];//每棵子树至少都要包含本身的值
    for(int i=head[x];i;i=e[i].next)//枚举第x节点的儿子
    {
        if(e[i].to!=fa)//判断是否搜回到父亲节点
        {
            int p=dfs(e[i].to,x);//x节点的一棵子树的最大价值
            if(p>0) sum+=p;如果子树价值大于0才要当前子树，不然就要剪去它
        }
    }
    ans=max(ans,sum);//用answer记录每棵子树的价值中的max
    return sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&f[i]);
        ans=max(ans,f[i]);//如果整棵树最后只剩下一个节点，那么那个点是这个最大的节点
    }
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        build(a,b);
        build(b,a);//因为是一棵树，所以建双向边
    }
    dfs(1,-1);//因为是一棵树所以随便找个点做根，一般我喜欢用1做根。一开始fa传入-1，因为没有-1这个点，且根没有父亲
    printf("%d",ans);
    return 0;
}