专栏文章
题解：P14637 [NOIP2025] 树的价值 / tree
P14637题解参与者 9已保存评论 8
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mimyk3j0
- 此快照首次捕获于
- 2025/12/01 17:39 3 个月前
- 此快照最后确认于
- 2025/12/01 17:39 3 个月前
不保证正确性。
ぼくにない想いもぼくにない強さもきみは持ってるんだよきっと セカイが待ってるきみにない涙もきみにない弱さもぼくは持ってるけどずっと セカイで待ってる悩みながらだって大丈夫立ち止まったって大丈夫ぼくらはまだここから歩いていける泣き顔もなんかいい感じ笑えたらもっといい感じ行こうよきみとぼくで
纪念一下第一道在正赛场切的黑题，也是最后一场正赛中场切的最难的题。
观察第一个样例，我们容易想到一个显然错误的贪心，就是说你一层一层贪心，每一层都放上你能放的最小值。
考虑这个贪心错在哪，观察第二个样例，你会发现第二个样例中如果你按这个方法贪心就会让右子树产生不了一点贡献，这和对根节点的贡献一对比显然不值。
然后你就获得了第二个不那么显然的假做法，让每个子树都取到自己的最大值，然后动态规划。你会发现取到最大值的时候答案好像一定不劣于贡献给根节点，很对哎。
然后你就会发现你过不了第二个大样例。
考虑原因，你会发现你让一个点的答案增加时可能使得它的祖先都增加上这个值，此时就不一定不劣了。
然后你考虑什么时候会更劣，你会发现如果它用第一种方法时会给上面的数带来 的贡献，而第二种则带来 的贡献。
还有你要注意如果没有一个满足的话你要枚举 在那一个地方因为 可能会给本身贡献一点答案。
然后你获得了第三个假做法。
假的原因是不一定会使祖先都加上这个值，如果加不上要反悔一下。
然后这个就是真的了。
但复杂度炸了，瓶颈在枚举 ，这个东西是简单的，你可以动态规划预处理出来。
可能有一些神秘特判细节，但大致是这样。
相关推荐
评论
共 8 条评论，欢迎与作者交流。
正在加载评论...