题解 P1122 【最大子树和】

FendtSilence · 2017-09-19 10:45:47 · 题解

这道题有一种最大子段和的感觉，因为没有确定的树根，所以最大的子树和可以作为其中任意的一段。

最大子段和的O(n)求法非常巧妙，方法就是从头记录一个子段和，当这个和小于0的时候，显而易见，这个子段对答案就没有贡献了，这个思想同样也可以运用到这个题目中

我们设f[i]表示这个点的最大子树的和，那么就可以用dfs求出它的儿子节点的子树的和，我们就只选取大于0的子树。

所以方程可以这么写f[i]+=dfs(i.son)[dfs(i.son)>0]初始化就是f[i]=a[i]

程序就非常好写了，细节上注意不要让儿子搜到自己的父亲就可以。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
const int maxn=16001;
int f[maxn],a[maxn];
bool vis[maxn];
vector<int>g[maxn];
int n,ans=-1;
int dfs(int u)
{
    vis[u]=1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i]; 
        if(!vis[v])
        {
            int x=dfs(v);
            if(x>0) f[u]+=x; 
        }
    }
    return f[u];
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],f[i]=a[i];
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    for(int i=1;i<=n;i++) ans=max(f[i],ans);
    cout<<ans;
}
int main()
{
    solve();
    return 0;
}