P8353 题解

· · 题解

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

注意：本题解做法使用 树剖。且该做法无法在大部分 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 的暴力解法）。