A41050. 生命之树 第一篇题解

这道题就是一道树形dp，非常基础。

请看我的极致简洁的AC代码：

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> h[110];
int a[110];
int dp[110];
//dp[u]表示以u为根最大子段和

void dfs(int u, int fa){//从u开始搜索，父亲是fa
    dp[u]+=a[u];
    for(auto v: h[u]){
        if(v==fa) continue;
        dfs(v, u);//一定要先处理儿子
        dp[u]+=max(dp[v], 0);//选择子树
    }
}

int main(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=0; i<n-1; i++){
        int u, v;
        cin >> u >> v;
        h[u].push_back(v);
        h[v].push_back(u);
    }//建图

    dfs(1, 0);//搜索

    int res=0;
    for(int i=1; i<=n; i++){
        res=max(res, dp[i]);
    }

    cout << res << endl;
    return 0;
}

求关注~