题解 P1122 【最大子树和】

Panole · 2016-09-29 22:28:24 · 题解

我可以说我的方法很奇怪吗？

但是跑的似乎也不慢，只有29ms，但是总感觉方法比楼下大神差多了（因为是第一眼的想法，本人比较差）

思路很玄学：

以f[i]表示以i为根节点的子树的美丽度的总和，min[i]表示在这棵以i为根节点的子树中，所能砍掉的美丽度的最小值（因为有-的）

那么答案就是让i从1~n扫一遍，求f[i]-min[i]的最小值即可。

我也不知道解释的能不能听得懂~

加个注释吧。。

#include<cstdio>
#include<cstring>
int head[160001],cnt,x,y,n;
long long f[160001],ans,min[160001];
bool bo[160001];
struct node
{
    int to,next;
}e[160001];
void addedge(int x,int y)  //建边
{
    e[++cnt].next=head[x];
    head[x]=cnt;
    e[cnt].to=y;
}
void dfs(int x) //递归求解min和f
{
    bo[x]=1;
    min[x]=0;
    if (head[x])
        for (int i=head[x]; i; i=e[i].next)
        if (!bo[e[i].to])
        {
            dfs(e[i].to);
            f[x]+=f[e[i].to];              //求解f，这应该不用说了吧
            if (min[x]<0)                  //求解min，min[x]=min(min[x],min[e[i],to]+min[x],min[e[i].to])
            {
                if (min[e[i].to]+min[x]<min[x]) min[x]=min[e[i].to]+min[x];
            }
            else 
                if (min[e[i].to]<min[x]) min[x]=min[e[i].to];
        }
    if (f[x]<min[x]) min[x]=f[x];
}
int main()
{
    scanf("%d",&n);
    for (int i=1; i<=n; i++) scanf("%lld",&f[i]);
    memset(head,0,sizeof(head));
    memset(bo,0,sizeof(bo));
    for (int i=1; i<n; i++)
    {
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    dfs(1);
    ans=0;
    for (int i=1; i<=n; i++)               //求答案
        if (f[i]-min[i]>ans) ans=f[i]-min[i];
    printf("%lld",ans);
    return 0;
}