题解 P1122 【最大子树和】

Joyce_Jiang · 2016-11-02 16:16:41 · 题解

这道题思路还是非常简单，简单的树形dp，先以1为根节点做一次，如果子树<0就不用加上去了，然后貌似有一个东西不加也能ac，就是一个换根计算的东西，，，不过好像这道题并没有什么用，，，，，，，

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,ans;
int head[20000],k;
int dp[20000],w[20000];
struct node
{
    int to,next;
}e[40000];
int dfs(int x,int fa)
{
    if(dp[x]>0)return dp[x];
    dp[x]+=w[x];
    for(int i=head[x];i;i=e[i].next)
        if(e[i].to!=fa)
        {
            dfs(e[i].to,x);
            if(dp[e[i].to]>=0)
            dp[x]+=dp[e[i].to];
        }
    ans=max(ans,dp[x]);
    return ans;
}
void change(int x,int fa)
{
    for(int i=head[x];i;i=e[i].next)
        if(e[i].to!=fa)
        {
            int temp=dp[x];
            dp[x]=temp-dp[e[i].to];
            dp[e[i].to]=temp;
            ans=max(ans,dp[x]);
            change(e[i].to,x);
            dp[e[i].to]=temp-dp[x];
            dp[x]=temp;
        }
}
void add(int u,int v)
{
    e[++k].to=v;
    e[k].next=head[u];
    head[u]=k;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    //change(1,0);
    printf("%d",ans);
}