自动搬运

查看原文

来自洛谷，原作者为

	lbw 若有 笃信之物 莫忘厮守

搬运于2025-08-24 22:44:27，当前版本为作者最后更新于2024-04-19 16:58:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一次见到只能用链分治做的题。

但是这题没有 spj 啊？？？

我们看到这题是构造+计算几何，感觉非常毒瘤。

首先观测到保证一定有解，让我们思考一下为什么一定有解。

如果在这里你就考虑到二叉树的性质，你就要寄了，因为这整题可以都不用到这个性质。

我们想随便选个点做根和根的对应点，然后极角排序，按极角序划分子树，可以保证两个子树的两边不会交。

精细实现可以做到 $\mathcal{O}(n^2)$。

然后我们发现这不是直接上点分治吗，但其实不是，因为我们发现上面的构造中子树的根不能乱选，不然 根-子树根 这条边可能会寄，必须选择例如极角序第一个点。

我们可以考虑链分治。

为什么呢，首先链分治是一个自上而下的过程，其次每个重链都只需要考虑链顶的父亲节点的影响，并且复杂度是对的。

我们考虑每个重链，根据套路，链分治对于重链也要分治。

设重链为 $x\to y$，选取点 $M\in[x\to y]$。

先分配 $x,y$，我们可以考虑选取最靠边的两个点，这样比较方便，具体的，选取凸包上相邻两个点即可。

设 $x,M$ 间一共有 $k$ 个点，对于 $x$ 的极角序中的前 $k$ 个点我们让他们对应 $x,M$ 间的点。

但是问题是如何保证 $x,M$ 这条边不会与里面相交呢？

我们可以发现只有如下的限制，设 $x,M,y$ 分别对应 $A,C,B$，则 $\Delta ABC$ 内不能有点。

我们再后面的点中选取 $B$ 使得角 $CBA$ 最小即可。

于是就做完了。

但是二叉树呢？？？？？

我们可以将中点改成带权中点，一通乱证可以得到时间复杂度少了一个 $\log$。