hdu 4219, 树形概率DP

题意:

  给定一颗树,每机在区间 [0,L] 中选择。求最终形成的树上任意两点间距离不超过S的概率。

解决:

  dp[以i为根][以j为叶子节点到i的最远距离] 当j*2<=s的时候,表示这个子树上的最长链不可能超过s,那么 可以任意取值就是当前的概率,但是为了保证j是精确的,所以要 减去距离小于等于j-1的概率; 当j*2>s的时候,这个子树必定有且仅有一个链的长度是s,那么 枚举该链,让其他链的长度任意取值,所有情况之和就是概率。

待补。

原文地址:https://www.cnblogs.com/takeoffyoung/p/4678551.html