题解 P4322 【[JSOI2016]最佳团体】

chenxia25 · 2021-02-02 12:50:44 · 题解

考虑二分 x，那么就是看是否有包含 0 的大小为 m+1 的连通块的 p-xs 和为正。

这个有一个很自然的 DP：dp_{i,j} 表示子树 i 内选 j 个的最大和。然后对于每个点扫描一下儿子，对每个儿子用类似卷积和背包的方式更新一下 DP 数组。这玩意被某沙雕称为「树的卷积」，和 SAO 那题一样，复杂度是平方的。

去年某天晚上绞劲脑汁，最终终于归纳证出来了这玩意的复杂度。现在一看，这 tm 不随便证？第二眼，哦，假了。只是不知道为啥所有人 & 题解都认为这个平方复杂度非常自然？希望神仙们在评论区解释一下。

那么总复杂度就是平方对数。