题解

思路

两只蝴蝶之间的距离等于它们路径经过的边数。由期望的线性性，可以对每条边分别计算“最终位于边两侧的蝴蝶对数”的期望，再除以 $\binom{k}{2}$。

把树根定为 $1$。对一条尚未处理的边，把树切成两部分。此前处理过的边都完全位于其中一侧，因而尚没有蝴蝶跨过当前边。当前边两侧的蝴蝶数仍是初始确定值。设包含输入端点 $u_i$ 的一侧有 $x$ 只蝴蝶，则当前贡献为 $x(k-x)$。

令 $p_v$ 表示处理到当前边之前，顶点 $v$ 有蝴蝶的概率。当前边尚未被处理，其两个端点此前依赖于两侧互不相交的随机方向，因此占用事件独立。

若蝴蝶从 $u_i$ 侧飞到 $v_i$ 侧，跨越当前割的蝴蝶数由 $x$ 变为 $x-1$，两两距离总和的变化量为

$$(x-1)(k-x+1)-x(k-x)=2x-k-1.$$

反向移动的变化量为 $k-2x-1$。两种移动的概率分别为

$$\frac12 p_{u_i}(1-p_{v_i}),\qquad \frac12 p_{v_i}(1-p_{u_i}).$$

处理这条边后，两个端点的占用概率都变为

$$p_{u_i}=p_{v_i}=\frac{p_{u_i}^{\rm old}+p_{v_i}^{\rm old}}2.$$

做法

子任务 1

枚举 $2^{n-1}$ 种边方向，按编号模拟所有移动，再用全源 BFS 得到的距离计算所有蝴蝶对的距离和。最后除以方向数和蝴蝶对数。

子任务 2

对每条边暂时删除它，从输入端点 $u_i$ 出发 BFS，直接统计这一侧初始有多少只蝴蝶。得到所有 $x$ 后，按上述概率公式转移。

满分算法

一次迭代 DFS 求父子关系和每个子树的初始蝴蝶数。对边 $(u_i,v_i)$：若 $v_i$ 是 $u_i$ 的儿子，则 $u_i$ 一侧有 $k-s_{v_i}$ 只蝴蝶；否则有 $s_{u_i}$ 只。先把所有 $x(k-x)$ 相加，再按边编号顺序加入两种移动的期望变化量并更新端点概率。

两套满分校验可以分别采用“初始总和加期望变化量”和“直接对 $x-1,x,x+1$ 三种最终割大小加权”两种等价写法。

正确性证明

对任意边，在它被处理前没有蝴蝶跨过该边，所以两侧蝴蝶数等于初始割计数。端点此前的随机过程分别只使用割两侧的边方向，故二者占用事件独立，移动概率公式成立。一次移动只改变跨越当前割的那只蝴蝶与其余 $k-1$ 只蝴蝶的距离，变化量正是上述两个式子。逐边累加期望变化，并用线性期望对所有割求和，得到最终所有蝴蝶对距离和的期望。再除以 $\binom{k}{2}$，即为随机蝴蝶对距离的期望。

复杂度

子任务 1 的时间复杂度为 $O(2^n n^2)$，空间复杂度为 $O(n^2)$；子任务 2 的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$；满分算法的时间复杂度和空间复杂度均为 $O(n)$。