题解：CF2035F Tree Operations

FRZ_29 · 2025-01-27 21:50:16 · 题解

更不好的阅读体验！

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

目标是使所有节点的权值变为 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 来完成。

• 假设当前的检查的操作数为 x。\mathcal{O}(n) 地计算所有节点的操作数，定义节点 u 的操作数为 f_u。
• 定义使以 u 为根节点的子树变为 0 的额外操作数为 h_u。使以 u 为根节点的子树变为 0 的总操作数为 need = \sum\limits_{v \in son(u)} h_v + a_i。
• - $need \lt f_u$，必然会有多余的操作，两次多余的操作间可以抵消，所以 $h_u = (f_u - need) \bmod 2$。 - 检查 $h_u$ 是否等于 $0$，等于 $0$ 说明操作次数为 $x$ 可行。

时间复杂度为 \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 次操作可以令整棵树的节点翻转。如果每 n 次操作，除了根节点 R 以外的节点全部翻转，那么会多出一次操作能用来使另一个节点保持原状，从而改变奇偶性，从而可以接近所有节点权值相同的情况。那么，此处最多为大致 n^2 次操作。
• 而如果此时 R 与其他值都不同。可以通过最差 n + 1 次操作改变：不改变 R，改变一个节点 2 次。如果全部是 1，再通过 n 次操作变为 0。

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

二分区间长为 (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)。代码。