[蓝桥杯 2015 省 B] 生命之树

题目链接

[蓝桥杯 2015 省 B] 生命之树

题目描述

在 X 森林里，上帝创建了生命之树。

他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。

上帝要在这棵树内选出一个节点集合 $S$（允许为空集），使得对于 $S$ 中的任意两个点 $a,b$，都存在一个点列 $a,v_1,v_2,...,b$ , 使得这个点列中的每个点都是 $S$ 里面的元素，且序列中相邻两个点间有一条边相连。

在这个前提下，上帝要使得 $S$ 中的点所对应的整数的和尽量大。

这个最大的和就是上帝给生命之树的评分。

经过 atm 的努力，他已经知道了上帝给每棵树上每个节点上的整数。但是由于 atm 不擅长计算，他不知道怎样有效的求评分。他需要你为他写一个程序来计算一棵树的分数。

输入格式

第一行一个整数 $n$ 表示这棵树有 $n$ 个节点。

第二行 $n$ 个整数，依次表示每个节点的评分。

接下来 $n-1$ 行，每行 $2$ 个整数 $u,v$，表示存在一条 $u$ 到 $v$ 的边。由于这是一棵树，所以是不存在环的。

输出格式

输出一行一个数，表示上帝给这棵树的分数。

输入输出样例

输入

5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

输出

8

数据范围

• $0\le n\le 10^5$，每个节点的评分不超过 $10^6$

解法：树形dp

按照题目的意思，我们实际就是要求子树的最大点权和。

我们定义 $f(i)$ 表示以节点 $i$ 为根节点的最大点权和。按照定义，我们最终返回的值为 m a x { f ( i ) } ( 1 ≤ i ≤ n ) max \{f(i) \} \ (1 \leq i \leq n) max{f(i)} (1≤i≤n)。

$j$ 是 $i$ 的子节点， f ( i ) = s c o r e [ i ] + ∑ j m a x { 0 , f ( j ) } f(i) = score[i] + \sum_{j}max\{ 0, f(j)\} f(i)=score[i]+∑j​max{0,f(j)} 。

由于 $S$ 可能是空集，也就是我们可能一个节点也不选，那说明 $0$ 也是答案之一。

最终答案为 m a x { 0 , f ( i ) } ( 1 ≤ i ≤ n ) max \{ 0, f(i)\} \ (1 \leq i \leq n) max{0,f(i)} (1≤i≤n)。

时间复杂度： $O(n)$

C++代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <functional>using namespace std;
using LL = long long;void solve(){int n;cin>>n;vector<int> score(n + 1);for(int i = 1;i <= n;i++) cin>>score[i];vector<vector<int>> g(n + 1);for(int i = 0;i < n - 1;i++){int a, b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);}vector<LL> f(n + 1);function<void(int, int)> dfs = [&](int u, int fa){f[u] = score[u];for(auto v:g[u]){if(v == fa) continue;dfs(v, u);f[u] += max(0LL, f[v]);}};dfs(1, -1);LL ans = 0;for(int i = 1;i <= n;i++) ans = max(ans, f[i]);cout<<ans<<'\n';}int main(){int t = 1;while(t--){solve();}return 0;
}