range pair LCA equal x query
rplexq = range pair LCA equal x query
这题就是各种平衡复杂度。
考虑朴素的做法。对
考虑对节点度数进行根号分治。
-
对于儿子数小于等于
\sqrt n 的x ，我们想办法对x 的每个询问都求出所有子树中编号在[l,r] 内的节点个数，然后计算答案。容易发现，我们相当于在做一个
O(n) 个点，O(m\sqrt n) 个询问的二维数点问题。为了平衡两边的复杂度，我们只需要使用分块前缀和的方式进行维护，这样单次修改
O(\sqrt n) ，单次查询O(1) 。那么二维数点部分的总时间复杂度为O((n+m)\sqrt n) 。但是要存下所有的询问，需要
O(m\sqrt n) 的空间复杂度。注意到对于一个x 的所有询问，它们所需要查询的子树都是一样的，而且 dfs 序区间连续且互不相交。因此我们数点时不具体记录每个询问，而是记录x ，处理时对这个x 计算答案。于是空间复杂度O(n+m) 。 -
对于儿子数大于
\sqrt n 的节点x ，这样的x 不超过\sqrt n 个。由于节点度数可能很大，因此我们不能逐个儿子进行查询。考虑枚举
x 每个儿子v ，并遍历v 所在子树，将子树中的节点都标记上v 。然后对于每个询问，我们考虑求出不合法的方案，即每棵子树内节点的平方和。容易发现这是一个经典的问题——小 Z 的袜子，可以使用莫队算法求解。遍历节点的总复杂度是
O(n\sqrt n) 没有问题，但是对于一个节点i ，莫队算法的复杂度是O(n_i\sqrt {m_i}) ，而n_i 的总和可以达到n\sqrt n ，因此是错误的。我们希望
n_i 的总和为n ，这样总的复杂度就为O(\sum n_i\sqrt{m_i})\leq O(\sum n_i\sqrt m)=O(n\sqrt m) 。考虑按 dfs 顺序处理询问，保证
x 处理的时候，x 子树中需要处理询问的节点均已处理完毕。在遍历节点时，我们分开记录之前的询问没遍历过的节点，和之前的询问遍历过的节点。
对于之前询问没遍历的节点，我们将它放到序列上，对
x 的询问，在这个序列上离散化后进行莫队。这样序列的总长度为O(n) ，则莫队的复杂度为O(n\sqrt m) 。对于之前询问遍历过的节点，我们对
x 的每个儿子节点开一个数据结构，支持快速区间求和。由于我们在最开始进行了根号分治，因此存在之前询问遍历过的节点的儿子不超过\sqrt n 个，所以只需要对这些儿子开数据结构即可。由于每个询问要查询这
\sqrt n 个儿子的信息，因此需要O(1) 的查询。想要做到O(1) 的查询则容易想到使用分块。朴素的做法对每个儿子开\sqrt n 大小的数组用于统计每个块内的节点个数，空间是可以承受的，但是还需要O(n) 大小的数组用于统计每个点的出现次数，这是无法承受的。注意到每个编号的点只有一个，因此我们可以直接开一个数组存这个点是否出现。空间复杂度O(n) 。这部分处理完以后，对分块数组进行前缀和统计，即可
O(1) 查询块的区间和。在处理询问的时候，对于之前询问没遍历过的节点，它们的信息通过莫队算法得到。对于之前询问遍历过的节点，我们对每个儿子分别统计：块间的只需要
O(1) 做块差分即可，共查询O(\sqrt n) 次，时间复杂度O(\sqrt n) 。边角的我们直接枚举，并对相应计数器加一，时间复杂度O(\sqrt n) 。然后再把这些儿子多出来的贡献加上去，时间复杂度O(\sqrt n) 。所以总时间复杂度O(m\sqrt n) 。
如果之前统计的是不合法方案，最后还需要一次二维数点来统计总方案。时间复杂度为
综上，这个算法的时间复杂度为