2022/04/02 做题记录

CF68D

可以发现只有 $hq$ 级别的点被增加过权制，于是我们可以开一个 map 记录每棵子树的权值和。

对于询问，我们可以用 dfs(x,mx) 表示考虑到 x 这个子树内的叶子，目前在外面已经被分配的联通块的权值最大值为 mx，于是我们这步有两种决策，把根节点和左子树分配成一个联通块然后把选中的叶子限制到右子树内，或者把根节点和右子树分配成一个联通块然后把选中的叶子限制到左子树内。

我们设当前点的权值为 $x$，左右子树的权值和分别为 $s_l,s_r$，注意到如果 $x+s_l < s_r$ 且 $x + s_r < s_l$，那么把两式相加有 $2x + s_l + s_r < s_l + s_r$，因为 x 为非负数所以这是不可能的。

在两种决策中有一种肯定会导致我们分配的这一块或者 dfs 中的 mx （因为剩下的一个子树中所有节点的权值和都小于新分配的这一块的权值和）是这另一个子树中所有叶子的答案，直接计算即可。

于是每次 dfs 只会进入一个子树，时间复杂度 $\text{O(h)}$。

code: /code/2022.4.2/CF68D.cpp