Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

树上期望距离

洛水·锦依卫 2019-01-29 08:21:00 阅读数:195 评论数:0 点赞数:0 收藏数:0

设:

  • \(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]=\frac{1+\sum (f[son]+f[i]+1)}{d[i]}\\ f[i]=\frac{1+d[i]-1+(d[i]-1)*f[i]+\sum f[son]}{d[i]}\\ f[i]=\frac{d[i]+\sum f[son] +(d[i]-1)*f[i]}{d[i]} \]
接着我们将右边的 \(f[i]\) 拆下来移项至左边:
\[ f[i]=\frac{d[i]+\sum f[son]}{d[i]}+\frac{(d[i]-1)*f[i]}{d[i]}\\ \frac{f[i]}{d[i]}=\frac{d[i]+\sum f[son]}{d[i]} \]
最后即可得到式子:
\[ f[i]=d[i]+\sum f[son] \]
这个式子很好懂,但是能不能更加简单呢?

由这个式子,我们可以得到每个节点到父亲节点的期望距离。同时我们观察这个式子,它的意思是,当前节点的 \(f\) 值为所有儿子的 \(f\) 值之和加上它的度数。那么我们来思考一下:

我们是如何计算 \(size\) ,即子树大小的?是不是如下的式子:
\[ size[i]=1+\sum size[son] \]
对于计算 \(size\) 的这个累加函数,我们可以理解为:每个节点的权值为 \(1\) ,子树内的权值和。当然,也可以理解为每个节点的大小为 \(1\) ,子树的大小。

那么我们再仔细端详这个式子:
\[ f[i]=d[i]+\sum f[son] \]
我们是不是可以理解为:每个节点的权值为 \(d[i]\) ,子树内的权值之和?

那么这个式子就可以变为:
\[ f[i]=\sum_{x\in 子树} d[x] \]
但是还不够,我们继续化简这个式子,考虑一下对于每条边,它对 \(d\) 数组的贡献。

\(d\) 数组为"度数",也就是当前点有多少条边。则我们可以理解为每条边会对两个点的度数有 \(1\) 的贡献。

那么子树内 \(d[i]\) 的和,我们就可以理解为计算边的贡献。由于子树内的边必定都连接着子树内的点,则每条边都为子树内的每个点的度数之和增加了 \(2\) 的贡献。而子树内的边数为 \(size[i]-1\) ,即每个节点向父亲都有且仅有一条边,那么子树内的边的贡献值和为:\((size[i]-1)*2\)

那么唯一的例外就只剩下了 \(i\)\(fa[i]\) 的这条边,由于 \(fa[i]\) 并不在子树内,所以它只会对 \(i\) 产生 \(1\) 的贡献。那么这个点就不能计算 \(2\) 的贡献。则加上子树内的贡献,我们可以得到最后的式子:
\[ f[i]=(size[i]-1)*2 \]
也可以写成:
\[ f[i]=size[i]*2-1 \]

父亲到儿子

至于父亲到儿子的话其实挺简单的 \(......\) 我们考虑就用之前的方法计算,如果以儿子为根重新建树,那么父亲到儿子的期望距离则为 \(size'[fa[i]]*2-1\)

当然不能重新建树 = = 。我们考虑如何得到 \(size'[fa[i]]\) ,那么就很简单了,\(fa[i]\) 相对 \(i\) 的子树,其实就是 \(i\) 相对 \(fa[i]\) 的子树以外的所有点。

那么 \(size'[fa[i]]=n-size[i]\) ,则我们设 \(g[i]\)\(i\) 的父亲到 \(i\) 的期望步数,那就有如下式子:
\[ g[i]=(n-size[i])*2-1 \]

距离计算

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

\(u->lca\)\(lca->v\)

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

那么长度肯定为:
\[ \sum_{i\in (u->lca)} f[i] +\sum_{i\in(lca->v)}g[i]-f[lca]-g[lca] \]
则我们可以使用树上前缀和记录每个点到根节点的 \(f\)\(g\) 之和,接下来就能够利用前缀和快速求出 \(\sum\) 的值了。

版权声明
本文为[洛水·锦依卫]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/luoshuitianyi/p/10332500.html

支付宝红包,每日可领(支付宝免费1-2元支付红包)