题解：P8999 [CEOI2022] Drawing

· · 题解

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

但是这题没有 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。