题目描述

竞赛中心 - 蓝桥云课 (lanqiao.cn)

题目分析 

本题使用树型DP，蓝桥杯官网出现了一个点的错误，但实际答案是正确的

状态表示：f[u]：在以u为根的子树中包含u的所有联通块的权值的最大值

假设s1，s2,…sk 是u的孩子

f[u]=w[u]+max(f[s1],0)+max(f[s2],0)+…max(f[sk],0)

从根结点开始深度优先遍历每个子结点

最后遍历每一个点的权值，找出最大的点即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, M = 2 * N;
int n, a, b, w[N], e[M], ne[M], h[N], idx;
ll f[N]; 
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int father)//存当前节点，当前节点的父亲节点（防止往回搜索） 
{f[u] = w[u];for(int i = h[u]; i != -1; i = ne[i])//寻找u所有的儿子 {int j = e[i];if(j != father)//如果j不是往回搜的 {dfs(j, u);//继续向下搜索 f[u] += max(0ll, f[j]);}}
}
int main()
{cin >> n;memset(h, -1, sizeof h); for(int i = 1; i <= n; i ++)cin >> w[i];for(int i = 1; i < n; i ++){cin >> a >> b;add(a, b);add(b, a);}dfs(1, -1); ll res = f[1];for(int i = 2; i <= n; i ++){res = max(res, f[i]);}cout << res;return 0;	
}