菜王的 blog

考虑 dp，设 $f_u$ 为喂饱 $u$ 子树所需的最小次数。对于叶子，令 $f_u = a_u$；对于有两个儿子 $v_0, v_1$ 的非叶子，$f_u = 2\max(f_{v_0}, f_{v_1}) - [f_{v_0} \ne f_{v_1}]$，因为两边次数不相等时，我们可以先操作需要次数更多的。

假设 $g_u = f_u - 1$，则转移变为 $g_u = 2\max(g_{v_0}, g_{v_1}) + [g_{v_0} = g_{v_1}]$。令 $dep_u$ 表示 $u$ 的深度（$dep_1 = 0$），$F_u = g_u \times 2^{dep_u}$，那么 $f_1 = F_1 + 1, F_u = \max(F_{v_0}, F_{v_1}) + 2^{dep_u}[F_{v_0} = F_{v_1}]$。

可以发现一个性质：$F_u$ 的二进制表示最多包含 $\log_2 nA$ 个 $1$（$A = \max a_i$）。通过归纳法证明：假设可以导致 $F_u$ 有 $k$ 个 $1$ 的树的最小大小为 $d(k)$ . 那么，当 $k \le \log_2 A$ 时，$d(k) = 1$；否则，$d(k) \ge 2d(k - 1)$，因为 $F_{v_0} = F_{v_1}$ 时才会出现新的 $1$。

维护一个由二元组 $(u, x)$ 组成的集合 $S$，其中 $x$ 是 $F_u$ 的一个下界。最初，将所有满足 $a_u > 0$ 的叶子 $u$ 的二元组 $(v, 2^{dep_u}(a_u - 1))$ 放入 $S$，如果 $S$ 中同时存在 $(p, x)$ 和 $(q, x)$（$p \ne q$），则将 $(r, x + 2^{dep_r})$ 放入 $S$，其中 $r = \text{LCA}(p, q)$，且 $2^{dep_r}$ 一定是一个新位（即加法一定不会发生进位）。

这样做为什么是正确的？考虑证明一个点的实际值一定不小于它的任何一个下界。对于任意一个 $p$ 的祖先 $o$（对于 $q$ 同理），显然有 $F_o \ge F_p$，则 $x \le F_p, F_q \le F_r$；若存在一个点 $z$ 在 $p \to r$ 转移的路径上，满足 $F_z > F_p$，那么 $F_z$ 的一个下界是 $F_p + 2^{dep_z} \ge F_p + 2^{dep_r}$，因为 $dep_z \ge dep_r$。

那么答案是 $S$ 中所有数对中最大的 $x + 1$（如果 $S$ 是空的，答案显然是 $0$）。

具体维护的时候，每当加入一个二元组 $(u, x)$ 时，我们只需要考虑 $x$ 相同，且 $u$ 与其 dfs 序相邻的两个 $u$，这样才能使其深度最大。设它们分别为 $p, q$，则我们要考虑 $y = \text{LCA}(u, p), z = \text{LCA}(u, q)$ 两个点，在这两者中取深度更大者，因为深度小的一定是深度大的的祖先，不需要考虑。设 $dep_y \ge dep_z$，则我们加入 $(y, x + 2^{dep_y})$，并重复上一流程。若找不到任意一个 $y$ 就跳出。

因为位数不超过 $\log_2 nA$，所以一次加入操作最多会插入 $\log_2 nA$ 个二元组，如果我们使用 std::vector<int> 维护有 $1$ 的所有位置，并用 std::set 维护二元组，则 std::set 的时间复杂度是 $O(\log n \log_2 nA)$。共操作 $O(\log_2 nA)$ 次，则单次加入或删除的时间复杂度为 $O(\log n \log_2^2 nA)$。若要更改 $a_u$，只需从 $S$ 中删除旧的 $a_u$ 所更新到的顶点对（类似于添加），然后添加新的 $a_u$ 所更新到的顶点对。总时间复杂度 $O((n + q) \log n \log_2^2 nA)$，不知道为什么可以通过。

code