小工具知识网

当前位置: 首页 > 行业知识 > 【洛谷 P8625】[蓝桥杯 2015 省 B] 生命之树 题解(深度优先搜索+树形DP)

行业知识

【洛谷 P8625】[蓝桥杯 2015 省 B] 生命之树 题解(深度优先搜索+树形DP)

2026-11-18 23:17:48 来源:互联网转载

[蓝桥杯 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下载问题

下一篇:非法入侵服务器怎么定义?