【构造，树】【Loj】Loj6669 Nauuo and Binary Tree

2023.7.3 Problem Link

交互库有一棵 \(n\) 个点的二叉树，你每次可以询问两个点之间的距离，猜出这棵二叉树。\(n\le 3000\)，询问次数上限 \(30000\)。

首先给你距离一定是先把每个点的深度问出来，确定一个大致的考虑顺序。

然后我们开始仔细思考“距离”这个条件怎么用。发现询问两个未知的点之间的距离没啥用，询问两个已知的点很蠢，于是只可能询问未知点和已知点之间的距离。

假设未知点是 \(u\)，已知点是 \(v\)，那我们就得到了 \(dep[\mathrm{lca}(u,v)]\)。进一步，\(v\) 已知，这意味着我们可以知道 \(\mathrm{lca}(u,v)\) 是哪个。

走到这一步这道题就很明朗了。我们希望进行一个类似于二分的过程，结合二叉树这一点，我们可以将考虑范围缩小到链往下的一棵子树内。这不就是重剖吗？做完了。

具体地，对于每个新点，对已知的树进行重剖，找到当前根所在重链的底端，询问新节点和它的距离，并改变当前节点。次数为 \(\sum_{i=1}^n \log i=O(n\log n)\)，并且常数很小，很符合题目限制。