生命之树
原题目链接
题目描述
在 X 森林里，上帝创建了生命之树。
他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。
上帝要在这棵树内选出一个节点集 S，使得对于 S 中任意两个点 a, b，都存在一个点列：
a, v1, v2, …, vk, b
使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点之间有一条边相连。
在这个前提下，上帝希望 S 中所有节点的整数和尽量大。
这个最大的和就是上帝给生命之树的评分。
注意：集合 S 可以为空。
输入描述
- 第一行一个整数 n，表示这棵树有 n 个节点。
- 第二行 n 个整数，依次表示每个节点的评分。
- 接下来 n-1 行，每行两个整数 u, v，表示存在一条 u 到 v 的边。
保证：
- 1 <= n <= 100000
- 每个节点的评分的绝对值不超过 1000000
输出描述
输出一行一个整数，表示上帝给这棵树的最大评分。
输入输出样例
输入
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
输出
8
c++代码
#include<bits/stdc++.h>
#include<stdio.h>using namespace std;typedef long long ll;ll n, a, b, ans = 0;
vector<ll> trees, dp, know;
vector<vector<ll>> edges;void dfs(ll root) {know[root] = 0;dp[root] += trees[root];for (ll x : edges[root]) {if (!know[x]) continue;dfs(x);if (dp[x] > 0) dp[root] += dp[x];}ans = max(ans, dp[root]);
}int main() {scanf("%lld", &n);edges = vector<vector<ll>>(n + 1);trees = vector<ll>(n + 1, 0), dp = vector<ll>(n + 1, 0), know = vector<ll>(n + 1, 1);for (ll i = 1; i <= n; i++) scanf("%lld", &trees[i]);for (ll i = 0; i < n - 1; i++) {scanf("%lld %lld", &a, &b);edges[a].push_back(b);edges[b].push_back(a);}dfs(1);cout << ans;return 0;
}//by wqs
思路解析
题目的意思就是要我们找一颗子树，使得这颗子树的权值和最大。
