CF280C Game on Tree

2020 年 10 月 29 日

1734 次浏览

664字数

<div class="list-group list-group-lg list-group-sp row" style="margin: 0"></div>(https://www.luogu.com.cn/problem/CF280C)

## Description

给出一棵树，每次随机等概率选择一未染黑的点，将它及其子树染黑。问期望多少次操作可以将树全部染黑。

## Solution

考虑一个点和它的子树被删除的方式

如果这个点被删除了，只有可能是它的父亲一直到根的儿子节点的路径上的某一条边被删除了。

假设现在要删的点是$u$, 深度为$dep_u$, 选中这条路上的边有$dep_u$条

因为我们只要删这条路上的一条边就可以把这个点删掉，所以期望是$E(u) = \frac{1}{dep_u} * 1$

所以答案是: $\sum_{u} \frac{1}{dep_u}$

注意$dep_{root}$要设成$1$

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 1e5 + 5;

int n, num;
int head[SIZE], dep[SIZE];
double ans, har[SIZE];

struct node {
	int to, nxt;
} edge[SIZE << 1];

inline int read()
{
	char ch = getchar();
	int f = 1, x = 0;
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
	return x * f;
}

inline void addEdge(int u, int v)
{
	edge[++ num].to = v, edge[num].nxt = head[u];
	head[u] = num;
}

inline void dfs(int u, int fa)
{
	dep[u] = dep[fa] + 1;
	ans = ans + har[dep[u]];
	for (int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if (v == fa) continue;
		dfs(v, u);
	}
}

signed main()
{
	n = read();
	for (int i = 1, u, v; i < n; ++ i) {
		u = read(), v = read();
		addEdge(u, v); addEdge(v, u);
	}
	dep[1] = 1;
	for (int i = 1; i <= n; ++ i) {
		har[i] = 1.00 / i;
	}
	dfs(1, 0);
	printf("%.6lf\n", ans);
	return 0;
}
```

最后修改：2021 年 09 月 04 日