行业知识
【洛谷 P8625】[蓝桥杯 2015 省 B] 生命之树 题解(深度优先搜索+树形DP)
[蓝桥杯 2015 省 B] 生命之树
题目描述
在 X ���林里,上帝创建了生命之树。
他给每棵树的每个节点(叶子也称为一个节点)上,都标了一个整数,代表这个点的和谐值。
上帝要在这棵树内选出一个节点集合 S S S(允许为空集),使得对于 S S S 中的任意两个点 a , b a,b a,b,都存在一个点列 a , v 1 , v 2 , ⋯ , v k , b {a,v_1,v_2, \cdots ,v_k,b} a,v1,v2,⋯,vk,b 使得这个点列中的每个点都是 S S S 里面的元素,且序列中相邻两个点间有一条边相连。
在这个前提下,上帝要使得 S S S 中的点所对应的整数的和尽量大。
这个最大的和就是上帝给生命之树的评分。
经过 atm 的努力,他已经知道了上帝给每棵树上每个节点上的整数。但是由于 atm 不擅长计算,他不知道怎样有效的求评分。他需要你为他写一个程序来计算一棵树的分数。
输入格式
第一行一个整数 n n n 表示这棵树有 n n n 个节点。
第二行 n n n 个整数,依次表示每个节点的评分。
接下来 n − 1 n-1 n−1 行,每行 2 2 2 个整数 u , v u,v u,v,表示存在一条 u u u 到 v v v 的边。由于这是一棵树,所以是不存在环的。
输出格式
输出一行一个数,表示上帝给这棵树的分数。
样例 #1
样例输入 #1
51 -2 -3 4 54 23 11 22 5
样例输出 #1
8
提示
对于 30 % 30\% 30% 的数据, n ≤ 10 n \le 10 n≤10。
对于 100 % 100\% 100% 的数据, 0 u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);ll ans = 0;for (int i = 1; i ans = max(ans, dp[i]);}cout
上一篇:解决Photoshop下载问题
下一篇:非法入侵服务器怎么定义?