神秘随机题。
众所周知：
\((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)\)。