甘孜州手机网站建设,关键词带淘宝的网站不收录,张家口网站建设电话,英文建站网站题目描述 在X森林里#xff0c;上帝创建了生命之树。 他给每棵树的每个节点(叶子也称为一个节点)上#xff0c;都标了一个整数#xff0c;代表这个点的和谐值。 上帝要在这棵树内选出一个非空节点集S#xff0c;使得对于S中的任意两个点a,b#xff0c;都存在一个点列 {a, …题目描述 在X森林里上帝创建了生命之树。 他给每棵树的每个节点(叶子也称为一个节点)上都标了一个整数代表这个点的和谐值。 上帝要在这棵树内选出一个非空节点集S使得对于S中的任意两个点a,b都存在一个点列 {a, v1, v2, …, vk, b} 使得这个点列中的每个点都是S里面的元素且序列中相邻两个点间有一条边相连。 在这个前提下上帝要使得S中的点所对应的整数的和尽量大。 这个最大的和就是上帝给生命之树的评分。 经过atm的努力他已经知道了上帝给每棵树上每个节点上的整数。 但是由于 atm 不擅长计算他不知道怎样有效的求评分。 他需要你为他写一个程序来计算一棵树的分数。
输入 第一行一个整数 n 表示这棵树有 n 个节点。(0n10^5) 第二行 n 个整数依次表示每个节点的评分。(每个节点的评分不超过10^6) 接下来 n-1 行每行 2 个整数 u, v表示存在一条 u 到 v 的边。 由于这是一棵树所以是不存在环的。 输出 输出一行一个数表示上帝给这棵树的分数。 样例输入 5 1 -2 -3 4 5 4 2 3 1 1 2 2 5 样例输出 8
解题思路 https://blog.csdn.net/CrazyMooo/article/details/109080562
代码如下
#include iostream
#include vector
using namespace std;
typedef long long LL;
const int N 100010;
LL w[N];
LL ans;//开LL不然会爆
vectorLLT[N];void dfs(LL root, LL fa) {for (int i 0; i T[root].size(); i) {int child T[root][i];if (child fa)continue;dfs(child, root);if (w[child] 0)w[root] w[child];}ans max(ans, w[root]);
}int main() {int n;cin n;for (int i 1; i n; i) {cin w[i];}for (int i 1; i n - 1; i) {int a, b;cin a b;T[a].push_back(b);T[b].push_back(a);}dfs(1, -1);cout ans endl;return 0;
}
