洛谷题单指南-树与图上的动态规划-P1122 最大子树和

原题链接：https://www.luogu.com.cn/problem/P1122

题意解读：在一颗树中，求一片连通区域最大的点权和（美味指数）。

解题思路：

树中的一片连通区域必然是以某个根节点为子树的一部分。

设f[i][0]表示以i为根的子树且不选i的最大美味指数，f[i][1]表示以i为根的子树且选i的最大美味指数

对于f[i][1]，已经选择了i节点，其子节点的选择就必要选f[j][1]>0的，因为要对i有正向影响；

对于f[i][0]，由于没有选择i节点，必然要在其所有子节点中选一个，选值最大的显然更合适，也就是对于所有的max(f[j][0],f[j][1])取最大值。

100分代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 20000;
int w[N];
vector<int> g[N];
int f[N][2]; // f[i][0]表示以i为根的子树且不选i的最大美味指数，f[i][1]表示以i为根的子树且选i的最大美味指数
int n, ans = INT_MIN;

void dfs(int u, int fa)
{
    f[u][0] = INT_MIN; //不选u时，子树的最大值
    f[u][1] = w[u]; //选u时，子树的最大值至少为w[u]、
    int maxChild = INT_MIN; //记录子节点的最大值
    for(int v : g[u])
    {
        if(v == fa) continue; 
        dfs(v, u);
        if(f[v][1] > 0) f[u][1] += f[v][1]; //如果选u，只有当前子节点值大于0，才应该选,因为可以给u加分
        maxChild = max(maxChild, max(f[v][0], f[v][1])); //更新子节点的最大值
    }
    f[u][0] += maxChild; //如果不选u，则子节点只能选最大的
    ans = max(ans, f[u][1]); //更新全局最大值
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 0); 
    cout << ans << endl;
    return 0;
}