给定一棵树,每条边的边权有一半的概率为1,有一半的概率为2,求这棵树直径的期望值.
 我们知道,如果我们得出了在每一个取值下的概率,那么我们就得出了期望,于是这一题可以转化为求概率的问题.
 显然的,这题我们需要使用树状DP求概率,那么我们又能愉快地讨论父亲结点的状态了,这个应该都很清楚有哪几种状态,就不用再多说了,不会的自己画一下就好.
 现在,我们不妨考虑这样的一个状态:
 表示,当前结点为,子树里以自己为端点的最长链为,子树里的最长链不超过的概率.
 那么,状态的合并就是讨论已经合并的子树里,以自己为端点的最长链为,子树里的最长链不超过的概率,与正在合并的子树里,以子树的根结点为端点的最长链为,子树里的最长链不超过的概率,同时也要保证合并之后的子树最长链仍然不超过,这可以用分步乘法原理来完成.
 double dp[55][150];
 double ans = 0;
 在你浏览本网站过程中,我会使用 Google analytics 与 百度统计 统计网站访问量,这个过程是基于匿名标识符的,并且可能会用于 Google 或 百度 方面的广告等,这将在未来被替换为我自己的匿名统计程序.