【题解】CF1438F Olha and Igor

CF1438F Olha and Igor

交互题。
给定一棵深度为 $h$ 的满二叉树，则其恰好有 $2^h-1$ 个节点。你可以进行以下询问不超过 $n+420$ 次：
选择三个互不相同的点 $u,v,w$，交互库将回答以 $w$ 为根的时候，$u,v$ 的 $\text{lca}$。
你需要回答原树的根。
$3\le h\le 18$。

$\texttt{Solution}$

为什么交互题都是神仙乱搞题啊......

首先上述的询问以 $w$ 为根的时候 $u,v$ 的 $\text{lca}$ 是在瞎扯，考虑一下 $\text{lca}$ 的意义，实际上这个点就是距离 $u,v,w$ 三个点距离和最小的点。

那么假设一个点作为根的时候，其三个儿子大小分别为 $s_1,s_2,s_3$（若本就是原树的根或叶子则不足的补 $0$）。那么询问回答这个点的方案数有：

$$s_1\times s_2\times s_3+s_1\times s_2+s_2\times s_3+s_1\times s_3$$

也就是当询问的三个点分别在三个子树内，或其中有一个是该点本身的所有方案数。

设原树根是 $\text{rt}$，其两个儿子分别为 $a,b$，我们可以来算算 $a,b$ 作为答案的方案数。

$$\text{cnt}_a \approx 2^{h-2}\times 2^{h-2}\times 2^{h-1}+2^{h-2}\times 2^{h-1}+2^{h-2}\times 2^{h-2}+2^{h-1}\times 2^{h-2}$$

那么如果所有方案数等概率出现，那么回答为 $a$ 或 $b$ 的概率应该约等于：

$$\approx \dfrac{\text{cnt}_a}{2^{3h}}$$

这个东西在 $3\le h\le 18$ 的时候，最小也是 $\dfrac{1}{5}$ 左右。在所有 $2^h-1$ 个节点中，他们两个作为回答的概率竟然都高达 $\dfrac{1}{5}$，所以考虑随机化算法。

随机 $420$ 组询问，将所有点作为回答的次数记录下来。取出出现次数最多的两个，我们认为他们两个就分别是 $\text{rt}$ 的儿子，记他们分别是 $p_1,p_2$。那么对于所有 $x$，询问 $(p_1,p_2,x)$，若回答正好是 $x$，则 $x$ 是根。

至于证明最大的两个都是 $\text{rt}$，我也不会 可以考虑算出根两个儿子的一共四个儿子作为回答的概率，通过上述算法可得大概在 $\dfrac{1}{10}$ 左右，那么剩下所有点作为回答的概率之和大概为 $\dfrac{1}{5}$。

假设这四个点中有一个成为了前二大，只需要四个点中有一个比根节点某一个儿子出现次数多即可，设这两个点分别出现 $p,q$ 次，那么这样的概率是：

$$\sum_{p>q} \Big(\dfrac{1}{10}\Big)^p\Big(\dfrac{1}{5}\Big)^q\Big(\dfrac{7}{10}\Big)^{420-p-q}\binom{420}{p,q}$$

这个东西通过电脑计算，概率大概在 $7\times 10^{-4}$ 的样子？这还是十分不准确的估计，实际概率应该更小吧。

所以直接随机 $420$ 组，得到 $p_1,p_2$ 再对每个点询问即可。时间复杂度 $\mathcal{O}(2^h)$。