「TC14102」DiameterOfRandomTree

Description

给出NN个点的树,每条边长会等概率是11或者22,问树的直径的期望。

HINT

N50N\leq 50

Solution

fi,j,kf_{i,j,k}表示ii子树内,最长链长度为jj,直径为kk的概率
gi,jg_{i,j}表示当前节点,算上之前算过的,最长链为ii,直径为jj的概率。

枚举aa,bb表示前面的子树最长链为aa,直径为bb;
枚举ccdd表示当前子树最长链为cc,直径为dd
gmxd,r=ta,b×fy,c,d×0.5g_{mxd,r}=\sum t_{a,b}\times f_{y,c,d}\times 0.5
tt数组就是个前缀和优化。

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch -'0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) x = -x, putchar('-');if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
void setIO() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w",stdout);
}
using namespace std;
const int N = 130;
int n;
int ver[N * 2], en, head[N], nxt[N * 2];
void addedge(int x, int y) {
ver[++en] = y, nxt[en] = head[x], head[x] = en;
}
double f[N][N][N];
void dfs(int x, int F) {
double g[N][N], t[N][N];
memset(t, 0, sizeof t);
t[0][0] = 1;
for(int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if(y == F) continue;
dfs(y, x);
memset(g, 0, sizeof g);
for(int a = 0; a <= n * 2; ++a)
for(int b = 0; b <= n * 2; ++b) if(t[a][b] >= 1e-8)// 前面最长链为a,直径为b
for(int c = 0; c <= n * 2; ++c)
for(int d = 0; d <= n * 2; ++d) if(f[y][c][d] >= 1e-8){ //y 最长链为c,直径为d
for(int x = 1; x <= 2; ++x) {
int mxd = max(a, c + x);
int r = max(b, max(d, c + x + a));
g[mxd][r] += t[a][b] * f[y][c][d] * 0.5;
}
}
memmove(t, g, sizeof g);
}
memmove(f[x], t, sizeof t);
}
int main() {
setIO();
n = read();
for(int i = 1; i < n; ++i) {
int x = read(), y = read();
addedge(x, y);
addedge(y, x);
}
dfs(1, 0);
double ans = 0;
for(int i = 0; i <= n * 2; ++i) for(int j = 0; j <= n * 2; ++j) ans += f[1][i][j] * j;
printf("%.7lf\n", ans);
return 0;
}