CF1438F 题解

problem & blog。

神秘随机题。

众所周知：

\((u,v)\) 的 LCA 是所有点 \(i\) 中 \(\operatorname{dis}(u,i)+\operatorname{dis}(v,i)+\operatorname{dis}(\text{root},i)\) 最小的。

对于一个点 \(u\)，设其有两个子树 \(T_1,T_2\)，它能作为 LCA 的方案数是 \(|T_1|\times|T_2|\times(n-|T_1|-|T_2|)\)。

• \(|T_1|=|T_2|=2^{h-dep_u}-1\)。
• \(n-|T_1|-|T_2|=(2^h-1)-2\times(2^{h-dep_u}-1)=2^h-2^{h-dep_u+1}+1\)。
• \(|T_1|\times|T_2|\times(n-|T_1|-|T_2|)=(2^{h-dep_u}-1)^2\times(2^h-2^{h-dep_u+1}+1)\)。
• 返回的 LCA 深度为 \(dep_u\) 的方案数为 \(2^{dep_u-1}\times|T_1|\times|T_2|\times(n-|T_1|-|T_2|)=2^{dep_u-1}\times(2^{h-dep_u}-1)^2\times(2^h-2^{h-dep_u+1}+1)\)。
• 返回的 LCA 深度为 \(dep_u\) 的概率为 \(\dfrac{2^{dep_u-1}\times(2^{h-dep_u}-1)^2\times(2^h-2^{h-dep_u+1}+1)}{\begin{pmatrix}2^h-1\\3\end{pmatrix}}\)。

这时我们就可以玩赖的了，扔 desmos 上观察，发现随到 \(dep_u=2\) 的概率比较大，即容易出现 \(\text{root}\) 的儿子。

• 先用 \(420\) 次乱随，记录每个点的出现次数。
• 找出最大和次大，它们极大概率就是 \(\text{root}\) 的儿子，记为 \(u,v\)。
• 暴力查询 \((u,v,i)\)，如果 \(\operatorname{query}(\{u, v, i\})=i\) 的话就代表 \(i\) 是根。输出即可。

代码，时间复杂度 \(O(n)\)。