RainAir
My OI Blog
RainAir
ZROI466小 G 的数

最近从某个地方看到了这个题。。。所以回来补一下题解。

题目描述

https://blog.aor.sd.cn/wp-content/uploads/2019/07/WX20190708-230728.png
https://blog.aor.sd.cn/wp-content/uploads/2019/07/WX20190708-230756.png

题解

直接求期望不太好求,我们可以考虑求出每一种条件下的概率,最后乘上直径长度就可以了。
我们设 $f_{i,j,k}$ 表示在以 $i$ 为根的子树里,目前不跨过 $i$ 节点的最长链是 $j$,子树的直径是 $k$ 的概率。
转移就用树 dp 合并子树那种方法来做…枚举一下根与待合并的子树之间的边权就可以了。
转移方程就咕了,详情请参考代码。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/648
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 NOIP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

ZROI466小 G 的数
最近从某个地方看到了这个题。。。所以回来补一下题解。 题目描述 题解 直接求期望不太好求,我们可以考虑求出每一种条件下的概率,最后乘上直径长度就可以了。 我们设 $f_{i,j,k}$…
扫描二维码继续阅读
2019-07-08
标签
近期评论