洛谷1122 最大子树和

access_time    bookmark 题解    comment 0 条评论    普及+/提高

大水题,题意就跟题目名一样,决策就是对于节点 $x$ 是否取当前搜到的儿子 $y$ ,显然要当前子树和要大于0我们才会取,然后dfs即可。

方程式:

$$f[x]+=max(f[y],0)$$

struct Edge{
    int next,to;
} edge[32005];
int s[16005],n,m,a,b,c,cnt,head[16005],w[16005],ans;

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int f)
{
    w[x]=s[x];
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs(y,x);
        if (w[y]>0) w[x]+=w[y];
    }
    ans=max(ans,w[x]);
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    dfs(1,0);
    printf("%d",ans);
    return 0;
}

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交的评论将在审核后显示。