囧仙 的博客

囧仙 的博客

P6782 迫真题解

posted on 2020-08-26 15:28:55 | under 题解 |

因为这是个过不去的做法,所以并不会交审核

考虑两个点的 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}$