题解 P6778 【[Ynoi2009]rpdq】

这里提供一个不知为何又 WA 又 TLE 的 sb 做法。 ~~想到分块的老哥好 nb 啊，可惜常数有点大~~ 首先可以想到一个技巧，将一个集合 $S$ 所有的点到根路径上各自加边权，然后询问 $\sum_{x\in S}\text{dis}(x,y)$ 就可以先预处理出所有的点到根路径的边权和 $val$，把这部分先算掉，询问 $y$ 到根路径的和，就可以得到 $\sum_{x\in S}val(\text{LCA}(x,y))$。 然后发现直接莫队复杂度端点移动要 $\log^2n$，用 $\text{LCT}$ 也要 $\log n$，自闭了。 ~~我个人猜想 lxl 不出边权都是 $1$ 应该是不让树状数组过。~~ upd: 已被官方打假 考虑二次离线莫队。因为询问个数达到 $n\sqrt{n}$ 级别，单次询问需要做到 $\mathcal{O}(1)$。 再考虑端点移动。显然用树剖+线段树已经不怎么行了，需要使用树剖+分块实现区间加。但是这样也需要 $\mathcal{O}(\sqrt{n}\log n)$。 upd: 具体的，要做到 $\mathcal{O}(1)$ 查询，可以维护块内标记，块内前缀和，大块的前缀和，每次查块内和大块的前缀和即可。 ~~这 TM 不是白想了吗~~ 但是有一个性质，虽然我们进行了 $\log n$ 次区间加，但是这些区间不相交，所以涉及的个数总和不超过 $n$。 这就启发我们在分块的时候继续平衡复杂度。 设块长为 $S$，每次边角是会跑满的，但是 $\log n$ 次区间加涉及的块只有 $\frac nS$，所以 $S\log n+\frac nS\ge 2\sqrt{n\log n}$，在 $S=\sqrt{\frac n{\log n}}$ 时取等。 但是树剖的 $\log n$ 是跑不满的，所以大可以将 $\log n=w$，总复杂度的瓶颈就是分块，时间 $\mathcal{O}(n\sqrt{nw})$，实际测试中 $w=2\sim 4$ 在随机数据中能跑到最优，~~但是 lxl 要是全出菊花+链+二叉树我就不知道了~~ 本来我以为 lxl 就是这么想的，结果有严格 $\mathcal{O}(n\sqrt{n})$，如果标算不是这个，看来这个会被卡爆了。 不过因为 $\log n$ 在根号里面，二次离线莫队的常数不大，大胆猜想 **精 细 的 实 现** 是可以过的。