这是本文档旧的修订版!
给定 $n$ 个点的树,点编号分别为 $1\sim n$。
初始时等概率随机选择一个点,接下来每次操作从未选择的且与已经选择的点相连的点中等概率随机选择一个点。
根据选择的顺序可以得到由点的编号构成的序列,问序列逆序对的期望个数。
首先枚举初始选择点,并将初始选择点作为根节点。
不难发现,每个节点只有在所以祖先结点被选取后才有机会选取。
同时对任意点对 $(u,v)$,当 $p=\text{LCA}(u,v)$ 被选取后,他们的其余祖先节点被选取的概率总是相等的。
于是不妨设 $u\gt v,d_1=d_u-d_p,d_2=d_v-d_p$,于是 $(u,v)$ 构成逆序对的概率等价于如下模型:
两个袋子中分别有 $d_1,d_2$ 个球,每次有 $t$ 概率从某个袋子中选一个球,也有 $1-2t$ 概率无事发生,问 $d_2$ 个球的袋子先被取空的概率。
不难发现 $\text{dp}(d_1,d_2)=\cfrac {\text{dp}(d_1-1,d_2)+\text{dp}(d_1,d_2-1)}2$。然后暴力统计固定根每个点对贡献即可,时间复杂度 $O(n^3)$。