TopCoder SRM677(Div.1) Normal DiameterOfRandomTree

Posted on By 二价氢

题目大意

给定一棵树,每条边的边权有一半的概率为1,有一半的概率为2,求这棵树直径的期望值。

解法

我们知道,如果我们得出了在每一个取值下的概率,那么我们就得出了期望,于是这一题可以转化为求概率的问题。

显然的,这题我们需要使用树状DP求概率,那么我们又能愉快地讨论父亲结点的状态了,这个应该都很清楚有哪几种状态,就不用再多说了,不会的自己画一下就好。

现在,我们不妨考虑这样的一个状态:

表示,当前结点为,子树里以自己为端点的最长链为,子树里的最长链不超过的概率。

那么,状态的合并就是讨论已经合并的子树里,以自己为端点的最长链为,子树里的最长链不超过的概率,与正在合并的子树里,以子树的根结点为端点的最长链为,子树里的最长链不超过的概率,同时也要保证合并之后的子树最长链仍然不超过,这可以用分步乘法原理来完成。

最后,将0位置上的答案全部加上来,记,则答案就是

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