1 条题解
-
0
题目分析
30pts
暴力枚举所有可能的联通块进行判定。
60pts
表示考虑了 及其子树内的所有点,且目前以 为根节点的一个联通块权值和恰为 时,可以得到的最多的联通块个数。
时间复杂度为 。
100pts
任选点权和为 的连通块,其中 ,那么该连通块至少包含两个点权非零的叶子,否则可以在不改变 的前提下迭代删去点权为 的叶 子。 如果至少有一个叶子的点权为 ,那么删去该叶子即可得到点权和为 的连通块。 否则所有叶子的点权都为 ,那么同时删去两个叶子即可得到点权 和为 的连通块。 因此可以通过树形 DP 求出总和为奇数/偶数的点权和最大的连通块来 判断是否存在点权和为 的连通块,每次一旦发现奇偶性正确且权值 则可以贪心直接断开,时间复杂度为 。
- 1
信息
- ID
- 128
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者