P9678 [ICPC2022 Jinan R] Tree Distance

· · 题解

CNBLOGS

洛谷

  • 给出一棵 n 个点的树，边有边权。

  • 记 \text{dist}(u,v) 为 u,v 两点简单路径上的边的权值之和。

  • 有 q 次询问，每次询问给出 l,r，求 \min\limits_{l\le i<j\le r} \text{dist}(i,j)。

称 (i,j)\,(i<j) 为一个点对，若把 \text{dist}(i,j) 看作改点对的权值，则我们要求解一个二维偏序问题。

现在的问题就是点对太多了，一共有 \mathcal{O}(n^2) 个。不过，真的需要这么多点对吗？比如现在有两个点对 (x_1,y_1) 和 (x_2,y_2) 满足 x_1\le x_2\le y_2\le y_1 且 \text{dist}(x_1,y_1)\ge \text{dist}(x_2,y_2)，你发现若查询的区间包含了 (x_1,y_1)，就一定包含了 (x_2,y_2)，而且 (x_2,y_2) 的权值更小。因此 (x_1,y_1) 这个点对是没有用的。我们称 \boldsymbol{(x_2,y_2)} 支配了 \boldsymbol{(x_1,y_1)}。

我们称一个点对为支配点对，当且仅当它不被其他点对支配。

考虑找出一个集合 T 包含所有的支配点对且大小可接受。我们来找一下一个点对成为支配点对的必要条件。

考虑点分治，对于一个支配点对 (i,j)，则一定存在一个分治重心 rt 满足 i,j 在 rt 不同儿子的子树中。不妨钦定 \text{dist}(i,rt)\le \text{dist}(j,rt)。设 S 表示当前联通块中满足 \text{dist}(x,rt)\le \text{dist}(j,rt) 且 x\ne j 的 x 构成的集合，则 \boldsymbol{i} 一定是 \boldsymbol{S} 中最大的 \boldsymbol{<j} 的数（前驱）或最小的 \boldsymbol{ >j} 的数（后继）。

为什么？考虑反证法，以前驱为例，设 j 的前驱为 pre，若 i<pre，根据 S 的定义可知 \text{dist}(i,rt),\text{dist}(pre,rt)\le \text{dist}(j,rt)。

此时一定满足：

你发现 (i,j) 被 (i,pre) 支配了。后继的证法类似，此处不再赘述。

考虑这样一个过程，对于每一层点分治，对于每一个点维护集合 S，并找到前驱、后继并将该点对加入 T。那么任意一个支配点对 (i,j)，点分治进行到使得它们在两棵不同子树中的联通块时，因为 i 一定是前驱或后继，那么对于 j 这个点找前驱、后继的时候，就把这个点对找到了。所以这样找到的 \boldsymbol T 集合包含了所有支配点对。

并且，由于点分治只会进行 \boldsymbol{\mathcal{O}(\log n)} 层，每一层每个点带来 \boldsymbol{\mathcal{O}(1)} 个点对，因此找到的总点对数量为 \boldsymbol{\mathcal{O}(n\log n)} 个。

具体地，如何实现这个构造 T 的过程？对于每一个联通块的点分治，将所有点 u 按照编号升序排序。正着反着扫一遍，维护一个随着 u 递增 / 递减，\text{dist}(u,rt) 不降的单调栈。那么对于一个点 v，它就是被它出栈的那些点的前驱 / 后继。

我们已经得到了集合 T，那么拿 T 中的点对去做二维数点即可。考虑离线 + 倒序扫描 i 保证 l\le i，用树状数组维护 j\le r 求前缀最值即可。至于 \text{dist}(i,j)，用树剖 + \text{LCA} 求一下即可。

时间复杂度为 \mathcal{O}(n\log^2 n+q\log n)，空间复杂度为 \mathcal{O}(n\log n+q)。

提交记录 代码