题解：P12153 【MX-X11-T7】「蓬莱人形 Round 1」信念

orz_z · 2025-05-03 19:47:20 · 题解

送的。

留给一些特别的做法。

留给已知存在的 \mathcal O(n\log^2 n) 做法，以及 \mathcal O(n\sqrt n) 做法。

长链剖分。

定义 ad_x 表示 x 到其 bfs 序下一个点的距离，则答案可以表示为邻域 ad 和减去右链 ad 和加上右链向左链的跳跃。

定义 mxd_x 表示点 x 子树内点离 x 的最大距离 +1。

当 k>mxd_x 时，(x,k) 邻域与 (fa_x,k-1) 邻域一致。

使用倍增进行跳跃操作，即当满足 k>mxd_x 时，进行一次跳跃，则最终的 (x',k') 满足 k'\le mxd_{x'}，所以 k'\le x' 所在长链点数，此时满足 k 小于等于 x 所在长链长度。

将 (x,k) 邻域分成 x 长链链顶节点的一个外邻域拼上 x 长链链顶子树内的部分。

那么我们对于一条长度为 len 的长链，如果能预处理其 \mathcal O(len) 外邻域信息，前半部分就解决了，总预处理信息量 \mathcal O(n)。

考虑这样一个结构：红线表示一条长链，横着表示长链上点的短链信息，那么处于同一条右斜上直线的点深度相同，且我们要考虑后半部分就是一个三角形状物。

这样一个三角形状物分成上下三角，进行扫描线求出所需的信息，同时注意到下三角就是正常树上长剖的过程。

对着树的长链划分从上往下做，每次做到一条长链，就完成长链上点的询问，以及其短链的信息预处理。

一个询问能直接由预处理信息和扫描线信息合并得出。

再考虑预处理部分，考虑一长链链顶 x，其父亲为 y，y 链顶为 z，现在要预处理 x 外邻域信息，可以分成 z 的一个外邻域（调用预处理信息）、z 长链内 y 子树外部分（可以扫描线求）、y 子树内除了 x 子树的部分。

用以上思想类似处理邻域 ad 和、减去右链 ad 和、右链向左链的跳跃这三部分的信息。

考虑领域 ad 和。

分别从上往下、从下往上处理上下三角信息即可。

对于“y 子树内除了 x 子树”的部分，处理好每个长链点的短链信息即可。

这部分复杂度 \Theta(n+q)，当然你也可以用点分治。

考虑右链 ad 和。

由于处理顺序是从上往下，我们可以定义信息为 (a,b)，分别表示当前统计到了深度 \le b 的部分，右链 ad 和为 a。

"z 长链内 y 子树外"的部分求的就是三角形状物中每一条右斜上直线最右上的点的 ad 和，对着这个左上斜线从左往右扫描线即可。

对于“y 子树内除了 x 子树”的部分，处理出每个长链点的右链信息即可。

移动一次会在某些深度加入新的点，用单点改区间查询的数据结构维护即可，这部分复杂度 \Theta((n+q)\log n)。

对于第三部分，同理，定义信息为 (a,b,c)，表示统计到了深度 \le b 的信息，右链跳到左链的距离和为 a，最深的一条跳跃为 c（最后求答案时最后一段信息是不需要的，但是统计的时候就需要记录上）。

"z 长链内 y 子树外部分"求的就是三角形状物中每一条右斜上直线最右上的点跳到下一深度的距离，此时将在长链右边挂着的短链长度改为左链长度减一和右链长度的最大值，扫描线即可。

“y 子树内除了 x 子树的部分“，需要讨论 x 子树在长链左、右侧，以及 x 右边最长链大小，来确定以 y 为 lca 的最大长度。

合并信息和上述讨论同理，复杂度 \Theta((n+q)\log n)。

这里可能做麻烦了。

把前面三部分答案合并即可，复杂度瓶颈在于倍增和扫描线的数据结构。

最终复杂度为 \Theta(n\log n)。