[集训队互测 2023] R9T2 道路建设

为什么 QOJ 上其他人都爆标还原了整颗树，而只有我傻傻改标算。

是不是做这道题的除了我都有脑子。

感觉像是完全对着硬 idea 出的，所以正常人做题想法根标方向完全不一样，但是涉及到的技巧都还是挺有用的哈！

题意大概是有一颗 \(2n\) 个点的树，你得知了前 \(n\) 个点构成的虚树形态，然后你能进行两类询问：

• 询问两点距离。询问次数限制 \(2n\)。

• 给出两个集合 \(A,B\) 和一个点 \(P\)，询问在以 \(A\) 中节点的每一个点作为根时，\(\text{LCA}(B)\) 是否是 \(P\)。需要满足询问次数 \(O(n)\)，\(\sum |A|,\sum |B|\) 都在 \(O(n\log n)\) 级别。

然后你需要构造一组大小为 \(n\) 匹配 \((a_i,b_i)\) 满足不存在 \(i\neq j\) 使得 \(\text{dis}(a_i,b_i)<\text{dis}(a_i,b_j)<\text{dis}(a_j,b_j)\)。

如果你是正常人，你会先想给定树形态怎么做。发现如果你取的点对距离均不超过 \(2\)，那么限制条件总会满足。容易在树上构造一组距离都不超过 \(2\) 的匹配方案。

如果你是正常人，那么你会考虑如何直接还原树形态。

如果你是正常人且强如 zhouhuanyi，那么你就可以想出一种基于问出深度对每一层分治的做法。

你发现这样题目中的限制条件一点意义都没有，所以这并不是出题人的意图。

题目中“匹配”的定义明显就是稳定婚姻问题：左部点更偏好距离大的点，右部点更偏好距离小的点，然后不能有匹配“私奔”。

由稳定婚姻解的存在性，这意味着你可以任取左右部的点集而都是有解的。

这样你直接取原来的 \(n\) 个点作为左部点，你的任务变成了求出左右部点两两间的 \(\text{dis}\)。

这个问题比确定所有点对的距离简单。这是因为你只需要知道后 \(n\) 个点在前 \(n\) 个点虚树上的位置而不关心后 \(n\) 个点的具体形态。你得到一个点是挂在两个点间还是一个点上后，你直接问出它到这两个点或这一个点的距离。然后你就可以确定一开始的虚树上每两个点的距离。（具体地，总有一个点在这两个点的路径上，所以将所有的到这两个点的距离之和取个最小值就行了）。

接下来你只需要解决定位节点问题就行了。我们考虑树上定位的一个经典想法：点分治然后判断其在哪个子树方向内。