先写一下自己想到的部分：
考虑枚举一个根。
计算一个点对出现的概率。
对于我这种期望概率基本不会的人，差点就把这题切了。
自己想到的部分都没有假。
问题在于：
如何计算一个点对出现的概率。
考虑和这两个点的\(LCA\)是有关系的，我们考虑把这两点到\(LCA\)的链拉出来。
如果有一次操作涉及了这两条链的话，那么他们弹出堆顶的概率都是\(\frac{1}{2}\)
所以我们可以预处理当两条链的长度固定的话，前者的底比后者底先取到的概率。
即\(f_{i,j} = \frac{f_{i - 1,j}\ \ \ +\ \ f_{i,j - 1}}{2}\)
直接算\(O(n^3log)\)
原文：https://www.cnblogs.com/dixiao/p/14958198.html