题目大意
给定一棵树，每条边的边权有一半的概率为1，有一半的概率为2，求这棵树直径的期望值。
解法
我们知道，如果我们得出了在每一个取值下的概率，那么我们就得出了期望，于是这一题可以转化为求概率的问题。
显然的，这题我们需要使用树状DP求概率，那么我们又能愉快地讨论父亲结点的状态了，这个应该都很清楚有哪几种状态，就不用再多说了，不会的自己画一下就好。
现在，我们不妨考虑这样的一个状态：
\(dp_{u, l, L}\)表示，当前结点为\(u\)，子树里以自己为端点的最长链为\(l\)，子树里的最长链不超过\(L\)的概率。
那么，状态的合并就是讨论已经合并的子树里，以自己为端点的最长链为\(l\)，子树里的最长链不超过\(L\)的概率，与正在合并的子树里，以子树的根结点为端点的最长链为\(l\)，子树里的最长链不超过\(L\)的概率，同时也要保证合并之后的子树最长链仍然不超过\(L\)，这可以用分步乘法原理来完成。
最后，将0位置上的答案全部加上来，记\(\sum\limits_l dp_{0, l, L} = P_{L}\)，则答案就是\(\sum\limits_L L(P_{L} - P_{L - 1})\)
Code
class DiameterOfRandomTree {
public:
vector<int> e[55];
double dp[55][150];
int max_mx;
void dfs(int u, int f, int mx) {
dp[u][0] = 1.0;
for (int v : e[u]) {
if (v == f) continue;
dfs(v, u, mx);
vector<double> nu(max_mx, 0.0);
for (int i = 0; i <= mx; i++)
for (int dy = 1; dy <= 2; dy++)
for (int j = 0; i + j + dy <= mx; j++) {
nu[max(j + dy, i)] += dp[u][i] * dp[v][j] * 0.5;
}
for (int i = 0; i < max_mx; i++)
dp[u][i] = nu[i];
for (int i = max_mx; i < 150; i++)
dp[u][i] = 0;
}
}
double getExpectation(vector<int> a, vector<int> b) {
for (int i = 0; i < (int)a.size(); i++) {
e[a[i]].push_back(b[i]);
e[b[i]].push_back(a[i]);
}
double ans = 0;
max_mx = a.size() * 2 + 1;
vector<double> r(max_mx, 0.0);
for (int i = 0; i < max_mx; i++) {
memset(dp, 0, sizeof(dp));
dfs(0, -1, i);
for (int j = 0; j <= i; j++)
r[i] += dp[0][j];
}
for (int i = 1; i < max_mx; i++)
ans += (r[i] - r[i - 1]) * i;
return ans;
}
};
Level Upper 2016 - TopCoder 500 : 4 / 5