题目概括征集中~
重金(5 RMB)征集状压 dp 解法~ @所有人
这题也太巧妙了叭! ——Mr.G
Solution 1 : $O(n^4)$
注意到节点 2 的父节点一定为 1;因此可以将以 2 为根的子树与剩余部分分开讨论。
定义状态 $f[i][j]$ 表示有 $i$ 个节点,深度为 $j$ 的方案数。
设以 2 为根的子树中共有 $x$ 个节点。情况一:子树 2 的深度恰好为 $j-1$,剩余部分的深度任意;情况二:子树 2 的深度任意,剩余部分的深度恰好为 $j$。
由于两棵子树的节点编号为 $3…i$ 间的任意整数,所以求出方案数之后需乘上标号的方案数。
$$
f[i][j]=\sum_{x=1}^{i-1}[\sum_{k=1}^{j}f[x][j-1]\times f[i-x][k]\times {i-2\choose x-1}+\sum_{k=1}^{j-2}f[x][k]\times f[i-x][j]\times{i-2\choose x-1}]
$$
对于期望,只需将 $\sum_{i=1}^n f[n][i]\times i$ 除以 $(n-1)!$ 即可。
对于四舍五入,可打表。(正经)
代码如下:
1 | #include <bits/stdc++.h> |
Solution 2 : $O(2^n*n^2)$
状压 dp 解法