题目描述P1122 最大子树和 dp
找到一个边界当做树的根，对每个节点采取保留，该节点的值dp[ x ] ,为f[ x ] 和 所有相连未访问过的节点最大和 对A点 dp[ A ] = f[ A ] + max(-1, 0) + max(3, 0) = -2 即选择A点， 对于A相连的节点，只要是大于0，都保留 去掉 -2 保留 3
对B点 dp[ B ] = f[ B ] + max(3, 0) + max(2, 0) = 1 也就是负的dp都去掉，保留非负dp
for(int i = 0; i < son[x].size(); i++){ s = son[x][i]; if(!vis[s]){ DP(s); dp[x] += max(0, dp[s]); dp[x] %= mod; } } #include <bits/stdc++.h> using namespace std; const int maxn = 16e3 + 5; const int mod = 2147483647; int n, f[maxn], dp[maxn], ans = -1e9; bool vis[maxn]; vector<int> son[maxn]; void DP(int x){ vis[x] = true; dp[x] = f[x]; int s; for(int i = 0; i < son[x].size(); i++){ s = son[x][i]; if(!vis[s]){ DP(s); dp[x] += max(0, dp[s]); dp[x] %= mod; } } // 不知道哪些会保留 我们就记录最大的值 ans = max(ans, dp[x]); } int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> f[i]; } int a, b; for(int i = 1; i < n; i++){ cin >> a >> b; son[a].push_back(b); son[b].push_back(a); } //找出一个边界 当作树的根节点 int edge; for(int i = 1; i <= n; i++){ if(son[i].size() == 1){ edge = i; break; } } DP(edge); cout << ans << endl; return 0; }