【题解】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)$。

添加新评论