[Codeforces235D] Graph Game

做法

看成每次删除一个点时会给它所在的连通块每个点一个贡献。

对每个点对 \((u,v)\) 计算 \(v\) 会给 \(u\) 一个贡献的概率, 加起来就是答案。

题目中给定的图是一棵基环树。

对于 \(u = v\),这个概率是 \(1\)。对 \(u \neq v\),分两种情况讨论:

一, \(u,v\) 在同一个子树中。把 \(u\) 看作根,那么这个概率就是,每次从还未被删除的点中选择一个点,将其子树删除,当 \(v\) 被删除时,\(u\)\(v\) 路径上除了 \(v\) 以外的点都还未被删除的概率。设总共有 \(n\) 个点,\(u\)\(v\) 路径上有 \(k\) 个点,类似猎人杀一题中的技巧,我们可以知道这个概率等于不断从 \([1,n]\) 中等概率随机取一个整数,一旦出现 \(v\)\(v\) 的祖先就停止,停止时除 \(v\) 以外 \(v\) 的所有祖先都未被删除的概率,即 \(\frac 1 n \sum_{i=0}^{\infty} (\frac{n-k}n) ^i = \frac 1 k\)

二,\(u,v\) 不在同一子树中,与情况一类似,但是不同的是此时 \(u\)\(v\) 有两条路径,只要其中一条存在就有贡献。可以容斥成第一条存在的概率加上第二条存在的概率减去两条都存在的概率。这三个问题都可以类似情况一地解决。

这样就在 \(\mathcal O(n^2)\) 的时间复杂度内解决了本题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>

using namespace std;

const int maxn = 3010;

double ans = 0;

int n, l[maxn], e = 0;
int deg[maxn], dep[maxn], a[maxn], tot;
vector<int> sub[maxn], son[maxn];

struct Edge {
int v, x;
} E[maxn<<1];

inline void addEdge(int u, int v) {
E[e].v = v, E[e].x = l[u], l[u] = e++;
}

void dfs(int u) {
sub[u].push_back(u);
for (int i = 0; i < son[u].size(); i++) {
int v = son[u][i];
dep[v] = dep[u] + 1;
dfs(v);
for (int _1 = 0; _1 < sub[u].size(); _1++) {
for (int _2 = 0; _2 < sub[v].size(); _2++) {
int x = sub[u][_1], y = sub[v][_2];
int d = dep[x] + dep[y] - 2 * dep[u] + 1;
ans += double (1) / d;
}
}
for (int _ = 0; _ < sub[v].size(); _++)
sub[u].push_back(sub[v][_]);
}
}

int main() {
memset(l, -1, sizeof(l));
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int u, v; scanf("%d%d", &u, &v);
++ u, ++ v;
addEdge(u, v), addEdge(v, u);
++ deg[u], ++ deg[v];
}
queue<int> Q;
for (int i = 1; i <= n; i++) if (deg[i] == 1) Q.push(i);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (deg[v] >= 2) {
-- deg[v];
if (deg[v] == 1) Q.push(v);
son[v].push_back(u);
}
}
}
for (int i = 1; i <= n; i++) {
if (deg[i] >= 2) {
int u = i, last = 0;
do {
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (deg[v] >= 2 && v != last) {
last = u;
u = v;
break;
}
}
a[++ tot] = u;
} while (u != i);
break;
}
}
for (int i = 1; i <= n; i++) {
if (deg[i] >= 2) {
dfs(i);
}
}
for (int i = 1; i <= tot; i++) {
for (int j = i+1; j <= tot; j++) {
for (int _1 = 0; _1 < sub[a[i]].size(); _1++) {
for (int _2 = 0; _2 < sub[a[j]].size(); _2++) {
int u = sub[a[i]][_1], v = sub[a[j]][_2];
ans += double (1) / (dep[u] + dep[v] + j - i + 1);
ans += double (1) / (dep[u] + dep[v] + tot - j + i + 1);
ans -= double (1) / (dep[u] + dep[v] + tot);
}
}
}
}
ans = ans * 2 + n;
printf("%.10lf\n", ans);
return 0;
}