题解：P13012 【MX-X13-T7】「KDOI-12」No one can be anything without comparison.

这个 12s, 2GB 看起来就让人很有做的欲望。NOI 前几天谁还做正经题啊。

不需要树分块，好像比正解简单一点？而且只需要保留一棵树的形态，剩下的的限制只要是区间包含单点就可以做。但是复杂度和正解相同，可能本质相同吧。（upd：确实本质相同，我的做法是将祖先关系描述成一个点子树的一段区间，另一个做法是将祖先关系描述成一个点到根的链，都是转化成了某种线性的结构）

本来以为是巨大数据结构的，写完发现超级好写，失策了。

先转化一下祖先的关系。放在 dfs 序上，设在第 $i$ 棵树上每个点的新编号是 $id_{i,j}$，每个点包含的编号区间是 $[l_{i,j},r_{i,j}]$（有 $id_{i,j}+1=l_{i,j}$）。那么一个有序对 $a_1,a_2,\cdots,a_k$ 合法等价于 $\forall 1 \le i \le k,id_{i,a_{i \bmod k+1}} \in [l_{i,a_i},r_{i,a_i}]$。

首先考虑 $\mathcal O(n^2)$ 左右的复杂度怎么做。这是一个环的限制，所以无论如何是需要枚举一个点的。枚举 $a_1$。设 $dp_{i,j}$ 表示走到第 $i$ 棵树的第 $j$ 个点的方案数。对于一个状态可以转移到一个区间，所以差分并还原即可。注意，转移后的下标是新编号，需要转化为原编号。

统计答案时，最后的限制是 $a_k$ 在第 $k$ 棵树上是 $a_1$ 的祖先。所以考虑解决这个限制。这里有两种思路，一种是从上到下 dfs，在 $a_k$ 处修改，$a_1$ 处查询，再撤销 $a_k$ 的贡献。另一种是 dsu on tree，$a_1$ 处修改，$a_k$ 处查询。先保留这两种思路，之后再看哪种更合适。

考虑 $k=3$ 怎么做。对于第一种思路，在 $a_1$ 处查询时 $a_2$ 是一段区间，贡献是 $a_2$ 对应的区间包含了多少个修改的 $a_3$。考虑分块，那么散块就是单点修改区间查询（可以使用 $\mathcal O(\sqrt{n})$ - $\mathcal O(1)$ 的分块平衡）。整块有很多区间，但值域只有 $n$，所以可以压缩信息。具体地，预处理，使用之前提到的做法求出每一个块对于每个 $a_3$ 的答案。对于每个 $a_3$ 的修改更新每个块的答案即可。对于第二种思路，思路其实是一样的。将 $a_1$ 的贡献分为整块和散块两部分，对于整块打上加一的 tag，散块区间加。查询 $a_3$ 时遍历每个块就可以算出整块的贡献，对于散块的贡献单点查询即可。

可以发现这两种思路本质是一样的。都是将贡献拆成整块和散块两部分，对于 $a_1$ 和 $a_3$ 在某一个整块上都有特定的贡献（$a_1$ 是 $1$，$a_3$ 是预处理的值），答案是将两者相乘。而散块就是将单点和区间的修改和查询的对应关系交换了，它们都是好做的。而第二种思路多一个 $\log$，所以接下来只考虑第一种思路。

可以发现整块的贡献可以扩展到 $k>3$，因为值域是 $n$，所以随时都在压缩信息，信息量不会随着树的个数而指数增加。而散块终究是不好做的。于是考虑将块长开很小，对于散块暴力枚举并递归到下一棵树的子问题。最开始我以为这样做的复杂度是 $\mathcal O(B^3)$ 的，于是可以设 $B=n^{\frac{1}{4}}$，就做完了。写完才发现递归到下一棵树的时候还需要枚举整块，在最后一棵树的时候会出现 $B^2\cdot \dfrac{n}{B}$，非常不牛。

能改进吗？考虑将第二棵树的块长开大一点，第三棵树的块长再开大一点，这样没准能平衡。设 $B_1,B_2,B_3$ 分别为三棵树的块长，那么运算次数是 $\dfrac{n}{B_1}+B_1\dfrac{n}{B_2}+B_1B_2\dfrac{n}{B_3}+B_1B_2B_3$。取 $\log$，从后到前依次取等，可以得到 $B_1=n^{\frac{1}{8}},B_2=n^{\frac{1}{4}},B_3=n^{\frac{1}{2}}$。这样就得到了 $\mathcal O(n^{\frac{15}{8}})$ 的优秀复杂度（而且还没算预处理的 $k^2$）。

我还真写了这个思路，甚至只跑了 40 多秒。其实确实合理，$\mathcal O(n^2)$ 估计就这么快，这个思路主要是为了压缩空间。

当我准备卡常的时候我突然看到了一段区间求和的代码。在递归的过程中完全不需要遍历整块！只需要在修改的时候动态维护前缀和即可。那为什么最初没发现呢？因为 $k=3$ 的时候块的个数与块长都是 $\sqrt{n}$，就没有区分它们，但是现在块的个数对复杂度产生影响了。所以要跳出思维定式。但是一步一步推过来想发现这一点对于我来说可能还挺难的。

于是这样的复杂度就是 $\mathcal O(\dfrac{n^2}{B}k^2+nB^3)$ 了。取 $B=n^{\frac{1}{4}}k^{\frac{1}{2}}$ 可以得到 $\mathcal O(n^{\frac{7}{4}}k^{\frac{3}{2}})$ 的复杂度。我取的是 $1000,80,30$，最后卡着时限过的。想要更快可能可以将整块的询问离线，这样可以优化空间访问。