题解 P1122 【最大子树和】

llllllllllll · 2018-12-09 16:42:09 · 题解

蒟蒻来写题解了……

（水平有限，欢迎大佬们指错Orz）

题目要求就是题目名，求最大的子树之和

所以先将树连起来（~~废话~~）

再将每个节点都找过去。如果被找的节点是叶子节点就将它删除，将它的值（与0比较的最大值）加到它的父节点，并去找他的父节点。

答案就是其中的最大值……

#include <cstdio>
#include <iostream>
using namespace std;
int fa[16001],so[16001],ma[16001],ans;
int n,m;
void fmax(int x)
{
    if (so[x]==0)
    {
        so[fa[x]]--;
        ma[fa[x]]+=max(ma[x],0);
        ans=max(ans,ma[fa[x]]);
        fmax(fa[x]);
    }
}
int main ()
{
    int i,j,k;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&ma[i]);
    }
    for (i=1;i<n;i++)
    {
        scanf("%d%d",&j,&k);
        if (!fa[j])
        {
            so[k]++;
            fa[j]=k;
        }
        else if (!fa[k])
        {
            so[j]++;
            fa[k]=j;
        }
    }
    for (i=1;i<=n;i++)
    {
        fmax(i);
    }
    printf("%d",ans);
}