题解 P1122 【最大子树和】

· · 题解

对于一棵树，它的最大子树有两种可能：1.根节点被加入；2.根节点未被加入。

对于情况1，设包含某一儿子（但不包含根节点）的最大子树为p，若p的权值之和>0，就把p连接到根节点上；如果p的权值之和<0，则没有必要把p连到根节点上。

当所有儿子被遍历一遍后，统计包含根节点的最大子树R的权值之和sum，如果sum>ans，那么ans=sum；

如果sum<=ans，就说明根节点没有必要加入。最大子树是某一个儿子的子集，其权值和为ans。

最后输出ans就好.

代码如下：

#include<cstdio>
#include<cstring>
#include<vector>
using std::vector;
const int maxn=16000+5;
int n,root_node,ans=0;
bool vis[maxn];//看看哪个结点没有加入到树中
vector<int> M[maxn],son[maxn];//M记录某个结点的相邻结点；son记录某个结点的儿子
int pa[maxn],a[maxn];//pa记录某个结点的父亲，a记录某个结点的权值
void build_tree(const int root_node)//用递归的方法构建一棵树
{
    vis[root_node]=1;
    for(int i=0;i<M[root_node].size();i++)
    {
        int p=M[root_node][i];
        if(!vis[p])
        {
            pa[p]=root_node;
            son[root_node].push_back(p);
            build_tree(p);
        }
    }
}
int work(const int root_node)//递归求解问题。该函数的意义是，返回包含root_node但不包含root_node父亲的最大子树的权值
{
    int i,sum=a[root_node],q;
    for(i=0;i<son[root_node].size();i++)
    {
        q=work(son[root_node][i]);
        if(q>0)sum+=q;
    }
    if(sum>ans)ans=sum;
    return sum;
}
int main(int argc,char **argv)
{
    int i,x,y,max_node;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        if(a[i]>ans)ans=a[i];//如果树中只有一个结点，那么这肯定是权值最大的结点
    }
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);//输入边
        M[x].push_back(y);
        M[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(max_node>M[i].size())
        {
            max_node=M[i].size();
            root_node=i;//找到一个度最大的结点(通过这种方式尽可能降低树的高度）
        }
    for(i=1;i<=n;i++)
        pa[i]=i;
    memset(vis,0,sizeof(vis));
    build_tree(root_node);//建立树
    work(root_node);//求解
    printf("%d\n",ans);
    return 0;
}