最大子树和

题目链接:最大子树和

题目描述:

小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题：
一株奇怪的花卉，上面共连有\(N\)朵花\(N−1\)条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。
老师想了一会儿，给出了正解。小明见问题被轻易攻破，相当不爽，于是又拿来问你。

输入格式:

第一行:一个整数n\((1 \le N \le 16000)\).表示原始的那株花卉上共\(n\)朵花
第二行有\(n\)个整数,第\(i\)个整数表示第\(i\)朵花的美丽指数.
接下来\(n-1\)行 每一行两个整数\(a,b\),表示存在a和b的枝条

输出格式:

一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过 \(2147483647\)

分析:

很明显的树型dp,但是这题没有明确告诉我们祖宗关系 所以我们要选定一个祖宗结点或者用,并且要建双向边.
状态表示\(f[i]\)记录以\(i\)为根的子树中,点权和最大的一颗子树
开始时,\(f[u]=a[u]\),接下来对于\(u\)的每颗子树我们都可以选择是否剪枝.
对于u的儿子v,如果\(f[v]<0\)那么就要剪掉u->v这条边().
那么状态转移方程:\(f[u]=f[u]+(f[v]>0?f[v]:0)(v为u的儿子)\)

注意:我们建的双向边,所以在遍历儿子的时候不能遍历到其父亲

#include<bits/stdc++.h>
using namespace std;
const int N  =1.7e4;
int f[N];
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>f[i];
    vector<vector<int>>adj(n+1);
    for(int i=1;i<n;i++)
    {
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<bool>vis(n+1,false);
    function<void(int,int)>dfs=[&](int u,int fa){
        for(auto v:adj[u])
        {   if(v!=fa)
            {   
                dfs(v,u);
                if(f[v]>0)f[u]+=f[v];
            }
        }
    };
    int res=-2147483647;
    dfs(1,0);
    for(int i=1;i<=n;i++)res=max(res,f[i]);
    cout<<res<<endl;
    return 0;
}