arrow_upward

洛谷1122 最大子树和 普及+/提高

@Llf0703  December 7, 2018
题目链接

大水题,题意就跟题目名一样,决策就是对于节点 $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;
}

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
This work is licensed under a CC BY-SA 4.0 International License .

本文链接:https://llf0703.com/p/luogu-1122.html

添加新评论