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

考虑二分 $x$，那么就是看是否有包含 $0$ 的大小为 $m+1$ 的连通块的 $p-xs$ 和为正。 这个有一个很自然的 DP：$dp_{i,j}$ 表示子树 $i$ 内选 $j$ 个的最大和。然后对于每个点扫描一下儿子，对每个儿子用类似卷积和背包的方式更新一下 DP 数组。这玩意被某沙雕称为「树的卷积」，和 SAO 那题一样，复杂度是平方的。  去年某天晚上绞劲脑汁，最终终于归纳证出来了这玩意的复杂度。现在一看，这 tm 不随便证？第二眼，哦，假了。只是不知道为啥所有人 & 题解都认为这个平方复杂度非常自然？希望神仙们在评论区解释一下。 那么总复杂度就是平方对数。