P1122 题解

· · 个人记录

又过了一道简单 dp，心情大好，写篇题解

简单树形 dp。Rt，要求的就是“最大子树和”。我们可以仿照“最大子段和”来设计状态：定义 f_i 为以 i 为根的最大子树和，所有 f_i 初始值为 a_i，转移方程也很像“最大子段和”，设 v 是 u 的孩子，则有

f_u=\max(f_v+f_u,f_u)

所有 f_u 的最大值就是答案。

#include <bits/stdc++.h>
using namespace std;
int n,u,v,ans=0xc0c0c0c0;//ans 必须赋值为极小负数，不能是0
int a[16001],f[16001];
vector<int> e[16001];
void dfs(int u,int fa){
    f[u]=a[u];
    for (int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if (v==fa){
            continue;
        }
        dfs(v,u);
        f[u]=max(f[u]+f[v],f[u]);
    }
    ans=max(ans,f[u]);
}
int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    for (int i=1;i<n;i++){
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}