题解：P8498 [NOI2022] 树上邻域数点

山田リョウ · 2026-03-05 23:27:27 · 题解

怒写 6.7k 代码通过。

先考虑建立一个静态 Top Tree，具体来说就是一个有 2n-3 个结点的满二叉（非叶子即二度）树，每个叶子对应一条边（作为一个簇），然后非叶子是由两个儿子对应的簇进行题面中的运算得来的，特别的，我们称题面中的点信息为界点，而点集是边信息中作为某条边的端点出现的所有点，那我们要求这里的簇除去界点外不能有向外的连边。

那可以发现 compress 可以用来合并重链上相邻的两端，而 rake 则是拼接轻子树，因此你全局平衡下（重链上只能加权分治，合并轻子树可以写哈夫曼树，当然我们发现加权分治写二分找分割点的话可以均摊到不带 \log，因此你对轻子树合并也写序列分治可以使得你的建树复杂度是线性，但是本题我们更希望结点深度和小一点，所以写哈夫曼）就可以做到树深度是 \mathcal{O}(\log n) 的。题外话是今年冬令营 lhx 介绍了一种可以减小最大深度的全局平衡手段，具体可以参考他的讲义。

再说回本题，建立出静态 top tree 后我们考虑模仿长剖求 k 级祖先的思想，先随便从一个端点是 u 的叶子跳到尽可能高使得其父亲簇不被当前邻域覆盖了（或者已经到根了），那由这里簇的性质可知邻域剩下的部分只能由两个界点向外的半邻域构成，且因为是极浅的所以两个半邻域半径都不能超过父亲簇大小，而考虑到这是二叉树所以父亲簇大小和与簇大小和同阶，均为 O(n\log n)，预处理下就可以 1 次合并回答询问了，因为你可以预处理时先把整个簇信息接某个半邻域上，这样只需要合并两个半邻域。

如何预处理呢，考虑类似长剖换根，先自下向上处理出簇内半邻域信息，再自上到下转移簇外半邻域，这样复杂度还是 O(n\log n)。

可能还需要略微卡卡常，就比如说你可以在 compress 和 rake 的过程中计算出簇直径，然后来减少预处理内邻域时循环上界。