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

· · 题解

怎么没人补（感觉也不是很难写。

先考虑 k = 3 的怎么做，然后再考虑怎么拓展，其实如果你是官方做法从 k = 3 拓展到正解是比较容易的。

题意大概是给了你 k 棵树，然后找 k 个点成环，相邻点在对应的树上呈祖孙关系，所以考虑先枚举 i_k，那么此时考虑 i_1，那么显然它在第 k 棵树上需要时 i_k 的子树，这个可以求出 k 的 dfs 序后改变为限制在一个区间内，下面考虑另一个方向的限制。

那么这个过程其实是：依次遍历 i = k-1 \rightarrow 1，初始化一个 u = i_k，每次将 u 在第 i 棵树上往上跳到 u 的一个祖先（不包含自己）。每次的决策不同就对应着一种可能的 i_1，一个 O(nk) 的 k 次树上前缀和就可以容易对单个 i_k 求出答案，但显然不优。

写一下我赛时 k=3 的做法，按第二棵树的 dfs 序考虑所有的 i_k，此时 dfs 序只需要每次进入节点 u 时插入 i_2 = u 的情况并在离开时删除即可，那么插入一个点 u 的过程实际上是继续枚举 i_1 为第一棵树上 u 的所有祖先，对每个 i_1 在第三棵树上的 dfs 序对应位置修改，这个用树状数组即可，现在难点是如何快速解决链修改的问题。

考虑树链剖分，先将这个路径转换为 O(\log n) 个链，然后考虑给每条重链分块，如果当前节点在某个块的块底，那么给这个块记录一个标记并直接跳到块首，否则就正常修改即可。查询时同时查询散的贡献并遍历每个块求出整块的贡献和，每个块到每个前缀的贡献系数可以预处理。设块长为 B，那么复杂度为 O(nB \log^2 n + \dfrac {n^2}B)，可以平衡到 O(n \sqrt n \log n)，如果用分块代替树状数组平衡复杂度应该也可以做到 O(n \sqrt{n \log n})，但实际上我赛时直接取的 B = \sqrt n 直接过了。

但不难发现这个做法无法拓展 k，我赛时以为后面是一些神秘的 meet-in-middle，但发现不是。

下面说正解，给第二棵树做树分块，设块长为 B，那么会标记 O(\dfrac nB) 个关键点，那么考虑在第二棵树上 i_2 到 i_3 的路径（不包括 i_3）是否经过某个关键点。

如果不经过，那么这样的 (i_2,i_3) 只有 O(nB) 个，直接存下来然后在第一棵树上 dfs 同时维护到根的链的信息，到点 u 时将 a_{1,i_2} = u 的数对拿出来更新答案，维护信息的部分是单点修改区间求和，可以用分块平衡实现 O(n\sqrt n + nB)。

如果经过，那么可以将 i_3 直接记录在它上面第一个关键点上（不难发现 i_3 一定会跳到这个点上），然后直接从关键点开始继续最前面说的暴力过程，由于前面说过可以 O(nk) 对单点求答案，这里直接这么做就行了，可以先预处理出每个关键点到最后第一棵树上的每个点的方案数，由于查询时区间，所以直接按第三棵树的 dfs 序排好并求前缀和，就能直接 O(1) 查询了，复杂度 O(\dfrac {n^2k}B)。

如果你真的理解了这个做法的核心思想，那么其实就不难发现怎么拓展了。它的关键就在于你可以花费并不太多的时间直接求出某个点的答案，因此直接分块即可。那么对于 k > 3 的情况也是一样，可以对第 2 \rightarrow k-1 棵树都树分块并找到关键点，并预处理对应的数组，我看官方题解的时候就总以为这里是用某种方式从前一棵树递推得来的，所以想了很久才明白，这里其实就是从头开始直接 dp 了一遍，和别的块的信息根本没关系。

考虑从每个 i_k 出发，直接 dfs，枚举每个下一个 i_{k-1} 并递归，但此时我们只需要找到它上面第一个关键点，找到后再往后的就可以直接用这个关键点的答案更新了，因此每个点的决策不超过 B，所以这个 dfs 的总复杂度不超过 O(nB^{k-2})，注意 i_k 是直接枚举的，而如果到了需要确定 i_1 的时候还没有碰到关键点我们就把 (i_2,i_k) 记录下来并类似前面所述的做法处理，因此这里只会 dfs k-2 层。

注意到真的把这些数对存下来也比较费劲，其实不需要，可以在需要找到 i_2 = u 的所有数对的时候直接再正着 dfs 一遍，实测这样比给每个点开 vector 存下来强。官方题解还说了个什么莫队？不懂。

那么前面预处理整块的复杂度是 O(\dfrac {n^2k^2}B)，散的部分是 O(nB^{k-2})。平衡复杂度 B = \sqrt[k-1]{nk^2}，但实际上的块长都偏小。我最后选择的是 400,80,30。500,100,40 也过了但比较卡时限，没前面那个快，代码没啥必要放了，也比较丑。