树上期望距离

Author Avatar
洛水·锦依卫 1月 27, 2019

树上期望距离

设:

  • $d[i]$:节点 $i$ 的度数
  • $fa[i]$:节点 $i$ 的父亲

我们分为两个部分:儿子到父亲与父亲到儿子。

儿子到父亲

我们先设 $f[i]$ 为 $i$ 到 $fa[i]$ 的期望移动步数。

显然,分为两种情况:

  • 一步走到父亲

对于这种情况,只需要走一步即可到达父亲节点,而这种概率为 $\frac{1}{d[i]}$ ,长度则为 $1$ 。那么贡献期望长度为 $\frac {1}{d[i]}$

  • 先走到 $i$ 的某个儿子,然后再走回来。

对于这种情况,贡献期望长度当然为:

(走到儿子的步数+儿子走到 $i$ 的步数+ $i$ 到父亲的步数)/ $d[i]$

由于现在走到儿子已经是个钦定的事情,那么步数为 $1$ ,而儿子走到 $i$ 的步数则必定为 $f[son]$ ,$i$ 到父亲的步数则一定是 $f[i]$ ,是不是看起来重复了 $f[i]$ ,挺绕的 ?

那么易得 $f[i]=\frac{1+\sum (f[son]+f[i]+1)}{d[i]}$ ,即是将两个情况的贡献加在一起。由于 $i$ 的儿子数肯定为 $d[i]-1$ 我们考虑化简这个式子,拆出 $\sum$ 中的 $1$ 与 $f[i]$ :

接着我们将右边的 $f[i]$ 拆下来移项至左边:

最后即可得到式子:

父亲到儿子

我们设 $g[i]$ 为 $i$ 的父亲移动到 $i$ 的期望步数,并设 $i$ 的父亲为 $x$ 。

那么有三种情况:

  • $x$ 直接一步移动到 $i$

这种情况下肯定为 $\frac{1}{d[x]}$ 的贡献。

  • $x$ 先移动到 $fa[x]$ ,然后再移动回 $x$ 再移动到 $i$

当然我们的长度肯定为:移动到 $fa[x]$ 的步数+$fa[x]$ 移动回 $x$ 的步数+ $x$ 移动到 $i$ 的步数

$=(1+g[x]+g[i])/d[x]$

  • $x$ 先移动到除了 $i$ 之外的其他儿子之一,再移动回 $x$ 再移动到 $i$

长度为:移动到儿子的步数+儿子移动回 $x$ 的步数+$x$ 移动到 $i$ 的步数

$=(1+f[son]+g[i])/d[x]$

那么贡献之和为:

由于 $x$ 除 $i$ 以外的儿子个数为 $d[x]-2$ ,那么可以如法炮制,像 $f$ 数组那样化简:

消项移项可得:

距离计算

对于给定的 $u->v$ 这样一条树上路径,我们可以拆成两条:

$u->lca$ 与 $lca->v$

对于第一条路径,肯定是全程向上的,对于第二条路径,肯定是全程向下的。

那么长度肯定为:

则我们可以使用树上前缀和记录每个点到根节点的 $f$ 与 $g$ 之和,接下来就能够利用前缀和快速求出 $\sum$ 的值了。