【膜树】(数学)

Description

求$n$个点带权完全图的生成树上,两点距离的期望。

$n\leq 1000$

题目解析

首先我们可以通过每条边在当前路径上的出现概率计算距离的期望。

对于边$(u,v)$,路径$(s,t)$

当两个端点重合时,$(u,v)$出现在路径中的概率即为其出现在生成树中的概率,因为每条边的次数相同,答案为$p1=\frac{(n-1)\cdot n^{n-2}}{\frac{n\cdot (n-1)}{2}}\div n^{n-2}=\frac{2}{n}$

当有一个端点重合时,$(u,v)$出现的概率为$p2=\frac{1-\frac{2}{n}}{n-2}=\frac{1}{n}$

当两个端点都不重合时,我们枚举$(u,v)$左右的生成树$p3=\sum\limits_{i=2}^{n-2}i^{i-2}\cdot (n-i)^{n-i-2}\cdot \binom{n-4}{i-2}$

现在对于路径$(s,t)$,它的答案就是$p1\cdot w(s,t)+p2\cdot (\sum\limits_{i=1}^{n}w(s,i)+\sum\limits_{i=1}^{n}w(t,i)-2\cdot w(s,t))+p3\cdot (totw-2\cdot(\sum\limits_{i=1}^{n}w(s,i)+\sum\limits_{i=1}^{n}w(t,i)-w(s,t)))$

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注