P6782 迫真题解

因为这是个过不去的做法，所以并不会交审核 考虑两个点的 LCA 为 $x$ 的必要情况，不难发现对于任意 $a,b$ 两个点，只要他们都是 $x$ 的孩子，且属于 $x$ 的不同子树，那么他们的 LCA 就必然是 $x$。 当然其实还有一种情况，就是 $x$ 在区间 $[l,r]$ 内，这样的话答案还要加上 $i,j = x$ 的情况，但是这个显然挺好算的。 也就是说，对 $x$ 的每个孩子 $s_1,s_2,s_3...s_l$ 统计其孩子编号在区间 $[l,r]$ 的总数，$c_1,c_2,c_3...c_l$，答案就是 $\sum\limits_{i = 1} ^ l \sum\limits_{j = i + 1} ^ l c_i \times c_j$ 不难发现这个东西就是 $(\sum\limits_{i = 1} ^ l c_i) ^ 2 - \sum\limits_{i = 1} ^ l c_i ^ 2 $ 再除以 $2$ 第一部分是很好算的，可以用线段树合并来解决，就是第二部分比较难计算 因为孩子比较少的时候可以去暴力统计，所以考虑根号分治 - 对于孩子个数小于 $n ^ \frac{2}{3}$ 的点 对他的每个孩子暴力统计 注意这个其实是可以 $O(1)$ 计算一个点的子孙中，编号在区间 $[l,r]$ 中个数的，只需要去弄一个分块合并之类的东西就可以了 - 对于孩子个数大于 $n ^ \frac{2}{3}$ 的点 因为至多只有 $n ^ \frac{1}{3}$ 个这样的点，所以可以对着这些点跑莫队 莫队的复杂度是 $n \sqrt m$，可以证明这些点莫队复杂度加起来不会大于 $n ^ \frac{5}{3}$