题解：CF2035F Tree Operations

可以说是官解的中文翻译了。

目标是使所有节点的权值变为 $0$。

最重要的是想到，如果 $m$ 次操作可以达到目标，那么 $2n + m$ 次操作也可行。

证明：在 $m$ 次操作的基础上先用 $n$ 次操作将所有节点变为 $1$，再用 $n$ 次操作把所有节点都变为 $0$。

这说明 $\forall i \in [0, 2n - 1],x \in\{x|x \bmod 2n = i\}$，$x$ 次操作对达到目标具有单调性。（后面将证明总是有解的）。

容易得到做法：遍历 $i\in[0,2n - 1]$，对集合 $\{x|x \bmod 2n = i\}$ 二分最小的能达到目标的 $x$（之后会证明二分的上下界，感性上来讲上界不会太大，上界到 $1\times10^{13}$ 次可过）。

对于二分的检查函数，可以通过 $\mathcal{O}(n)$ 的树型 dp 来完成。

时间复杂度为 $\mathcal{O}(n^2\log V)$，$V$ 为二分上界。代码。

本题可以通过确定二分上下界优化成 $\mathcal{O}(n\log na_i+n^2\log n)$。同时能证明总是有解。

先解决一个更为简单的问题。使树上所有节点的权值不大于 $0$ 的最小操作数。与上述树形 dp 的流程大致相同，只是当 $need \lt f_u$ 时令 $h_u = 0$。

可以二分出一个下界 $t$。同时对于原问题，$t$ 次操作后可以令原树的节点的权值全部变为 $0$ 或 $1$，原问题的下界肯定不小于 $t$，这很显然。且上界不大于 $t + n^2 + 2n + 1$。接下来仅考虑最坏情况。考虑将所有节点的权值变为同一个数。

确定上下界后和原来一样二分就好。

二分区间长为 $(n + 1)^2$，找出 $t$ 的时间复杂度为 $\mathcal{O}(n\log (n\max\limits_{i = 1}^{n}(a_i)))$，最后二分的时间复杂度为 $\mathcal{O}(n\log n^2)$。总复杂度为 $\mathcal{O}(n\log (na_i) + n\log n)$。代码。