[计数] [点分治] P7126 [Ynoi2008] rdCcot

· · 题解

题意：n 点的树，建一个新图，x,y 有边当且仅当树上两点距离 \le d，m 次询问，求只保留 [L,R] 的点图上连通块数量。n\le 3\times 10^5,m\le 6\times 10^5。

这个图比较复杂，有种思路：保留有限信息刻画连通块。那么可以考虑钦定代表元。

也许是通过手玩，发现一定有一个点连向连通块上所有点。不难发现树上最浅的点一定满足条件，这是因为对于 dep_x<dep_y<dep_z，若 dis(x,y)\le d,dis(y,z)\le d 则 dis(x,z)\le d，画一下图就知道了，然后根据这个类似转递性的东西就能证明了。

所以按深度给排名，记为 p_i，用 bfs 序即可，那么让 \min p 成为代表元。

拆贡献，考虑一个点成为代表元的条件是不存在其它点距离它 \le d 且 p 比它小。所以一个点可以贡献的区间 [L,R] 满足 l_i\le L\le x\le R\le r_i，算答案就是二维数点了。

$O(n\log n+m\log n)$。