题解

思路

利用期望的线性性，分别计算每一对编号 $u>v$ 中，$u$ 比 $v$ 更早被标记的概率，再把这些概率相加。

固定最初被标记的根 $r$，把树看成以 $r$ 为根的有根树。设 $w$ 为 $u,v$ 的最近公共祖先，$x=\operatorname{dist}(w,u)$，$y=\operatorname{dist}(w,v)$。从 $w$ 已被标记开始，两条通往 $u,v$ 的路径各有一个“下一结点”等待被选。忽略其他选择后，下一个来自这两条路径的结点等概率属于任意一侧。

做法

令 $f_{x,y}$ 表示两条路径还分别剩余 $x,y$ 条边时，先到达第一条路径终点的概率。边界为

转移为

预处理全部 $f$。随后枚举初始根和所有 $u>v$，求出最近公共祖先与两段距离并累加 $f_{x,y}$。最后除以根的数量 $n$。

极小规模可以对已标记结点集合做完整概率动态规划；较小规模可以对每个根与编号对单独建立二维吸收状态，不复用通用概率表。

正确性说明

对于固定的根和结点对，最近公共祖先必先于两结点被标记。在两条目标路径都未结束时，每条路径恰有一个当前边界结点。其他边界结点的选择不会改变两条路径的剩余长度；在下一次选中两条目标路径之一时，两边对称且概率各为二分之一，因此递推精确给出 $u$ 先于 $v$ 的概率。期望线性性保证把所有 $u>v$ 的该概率相加，恰为逆序对数量的期望。再对均匀选择的初始根取平均，即得答案。

复杂度

预处理概率表为 $O(n^2)$。对每个根建立祖先信息并枚举结点对，总时间复杂度 $O(n^3\log n)$，空间复杂度 $O(n^2)$。