自动搬运

查看原文

来自洛谷，原作者为

	yzy1 Меня мое сердце, в тревожную даль зовёт.

搬运于2025-08-24 22:38:20，当前版本为作者最后更新于2022-05-19 19:38:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

「另，这题和树剖一分钱关系都没有。」——出题人。

注意：本题解做法使用 树剖。且该做法无法在大部分 OJ 上评测。但理论上考试本地评测时可通过。且允许在考场使用。

Upd. 5/27: 感谢 @liuzhangfeiabc，目前已找到一种可以在洛谷和 LOJ 通过的方式。

Subtask $\bf 1$

暴力即可。用一个数组存点权，另一个数组存父亲，每次修改时暴力跳父亲修改。

Subtask $\bf 2$

该点满足特殊性质：点 $i$ 的父亲均从 $1\sim i-1$ 中均匀随机产生。

可以证得这样生成的树以 $1$ 为根的期望高度是 $O(\log n)$ 的。具体证明过程可以参考 EI 的证明。

由于树高期望 $O(\log n)$，所以链长也期望 $O(\log n)$。故该测试点仍可暴力。

Subtask $\bf 3 \sim 16$

该点满足特殊性质：树退化为链。

链上的区间加区间和可以用多种数据结构维护。但是此处由于内存卡的较紧，仅能开下两个长度为 $n$ 的 $32$ 位整形数组。所以这里使用额外空间 $O(\sqrt n)$ 的分块维护。

Subtask $\bm{{n \le 3 \times 10^6}}$

树上问题的一种维护方式就是树剖。轻重链剖分的大众写法需要开 fa、sz、dep、hson、top、dfn 六个数组。本题中显然无法开下。考虑将每个数组用于多种用途。我们发现，sz、hson、top 三个数组可共用一个数组。且由于题目保证 $f_i < i$，深搜的过程可以直接用 for 加上一个 bitset 代替。同时由于 $f_i < i$，即已经确定拓扑序，dep 数组是无必要存在的。跳链时只需要比较链顶的 dfn 即可。

树剖完成后同样用分块维护。空间是 $4n+O(\sqrt n)$ 级别的。

Subtask $\bm{{n \le 4 \times 10^6}}$

如果你做过 MCOI R4A，你可能会知道一个时间换空间的方法。可以参考 该题解 中的「优化 A」部分。

我们发现 Subtask ${n \le 3 \times 10^6}$ 做法中的 fa、top、dfn 三个数组值域全是 $O(n)$。可以使用 23 个 bit 来存一个 int。这样就可以通过该 Subtask 了。

分块块长为 $800$ 时，空间约为 $(4n+3\times\frac{23}{8}n+2\times \frac{n}{800})\text{ B}$。

Subtask $\bm{{n \le 6 \times 10^6}}$

树剖的三个辅助数组还是太多了，能改成两个吗？

当然可以。我们发现，树剖在跳链的过程中，对于一个是某个节点的重儿子的节点只会从它跳到链顶，否则只会从它跳到它的父亲。考虑把 fa 和 top 存到一起，使用 bitset 存储每个点是否是一条链的链顶。然后我们就可以少开一个数组而通过该 Subtask 了！

分块块长为 $800$ 时，空间约为 $(4n+2\times\frac{23}{8}n+\frac{n}{8}+2\times \frac{n}{800})\text{ B}$。

Subtask $\bm{{n \le 7 \times 10^6}}$

把 $n=7\times 10^6$ 带入上面式子，得到内存约 $69300000\text{ B}$，就差一点了！

观察题目中的这个强制在线形式，发现所有输入会异或答案对 $2^{20}$ 取模后的结果。考虑只存 $a$ 数组的低 $21$ 位，然后像 Subtask ${n \le 4 \times 10^6}$ 那样做。

可以发现此时内存可以开下了。但是我们只有答案的低 $20$ 位能做些什么呢？

注意此时我们可以得到所有解密后的询问，并以 $O(q)$ 的空间复杂度把它们存储下来。我们可以直接询问离线，把虚树建出来，然后重新在虚树上跑一遍树剖就行。

问题来了，fa 数组已经不存在了，如何还原树的形态呢？

如果是在 OJ 上测评，且 OJ 允许操作文件指针，则可以使用 fseek(stdin,0,SEEK_SET); 让文件指针回到文件开头重新读取。如果是在本地，使用文件输入输出，我们可以直接 fclose 把文件关了后重新 freopen 打开再读一遍。

做完第一遍后，记录解密后的数据，并且把内存池整个清空，重新分配内存，重新再做第二遍。

该做法在 Arch Linux 上的 LemonLime 0.3.3 测试，编译器为 G++ 11.3.0，编译选项 -std=c++11 -O2，评测机 CPU 为 Intel i5-8259U。经测试程序运行内存为 $62.8\text{ MB}$。可以通过。

代码参考（包含最终解法和题解中说明的大部分 Subtask 的暴力解法）。