CF917D 题解
Link
用一下 CF156D 的结论，即将 \(k\) 个连通块连起来有 \(n^{k-2} \prod\limits_{i=1}^ks_i\) 种情况。
这道题目要让求和树共享 \(k\) 条边的树的个数。似乎也可以套用上述公式。
设 \(f(x)\) 表示恰好和原树共享 \(x\) 条边的方案数，\(g(x)\) 为至少共享 \(x\) 条边的方案数。
很明显可以使用二项式反演。
即：
\[\begin{aligned}
f(x)=\sum_{i=x}^{n-1}(-1)^{i-x}\binom{i}{x}g(i)
\end{aligned}
\]
现在来考虑 \(g\) 函数的求法。
我们可以先删去一些原来树上的边，再利用上述结论（相当于就是乱连），求出 \(g\)。
详细的说，我们要求对于每一个 \(i\) ，求出对于每一种将树分成 \(n-i\) 个连通块的方案，\(\prod\limits_{i=1}^{n-i}s_i\) 的和。
考虑树上dp。
Solve 1
令 \(dp_{i,j,k}\) 表示在 \(i\) 的子树中划分了 \(j\) 个连通块，\(i\) 这个连通块大小为 \(k\) 的乘积的和（没有乘当前连通块）。然后考虑转移。
\[\begin{aligned}dp_{u,x,a}\cdot dp_{v,y,b}\cdot b \to dp'_{u, x+y, a}
\\dp_{u,x,a}\cdot dp_{v,y,b} \to dp'_{u, x+y-1, a+b}\\
\end{aligned}
\]
时间复杂度 \(O(n^3)\)。
Solve 2
考虑 \(\prod\limits_{i=1}^{k}s_i\) 的组合意义：在每一个连通块中选择一个点的方案数。
重新定义状态。
令 \(dp_{i,j,0/1}\) 表示\(i\) 的子树中划分了 \(j\) 个连通块，\(i\) 连通块有没有选点（\(0\) 为不选，\(1\) 为选）。
考虑转移。
\[\begin{aligned}
dp_{u,x,0}\cdot dp_{v,y,1} \to dp'_{u, x+y, 0}\\
dp_{u,x,1}\cdot dp_{v,y,1} \to dp'_{u, x+y, 1}\\
dp_{u,x,0}\cdot dp_{v,y,0} \to dp'_{u, x+y-1, 0}\\
dp_{u,x,1}\cdot dp_{v,y,0} + dp_{u,x,0}\cdot dp_{v,y,1}\to dp'_{u, x+y-1, 1}\\
\end{aligned}
\]
时间复杂度 \(O(n^2)\)。
然后就做完了。
Solve 3
代码：
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 105;
const int Md = 1e9 + 7;
vector<int> vec[N];
ll n, dp[N][N][2], siz[N], f[N][2], C[N][N];
ll Pw[N], g[N], ans[N];
signed main() {FASTIO;cin >> n;for (int i = 1; i < n; ++i) {int u, v; cin >> u >> v; vec[u].emplace_back(v);vec[v].emplace_back(u);}function<void(void)> init = [&](void) -> auto {C[0][0] = 1;for (int i = 1; i < N; ++i) {C[i][0] = 1;for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Md;}Pw[0] = 1;for (int i = 1; i < N; ++i)Pw[i] = (Pw[i - 1] * n) % Md;};init();function<void(int, int)> dfs1 = [&](int u, int fa) -> auto {siz[u] = 1;dp[u][1][0] = dp[u][1][1] = 1;for (auto v : vec[u]) {if (v == fa) continue;dfs1(v, u); for (int j = 1; j <= siz[u]; ++j) {for (int k = 1; k <= siz[v]; ++k) {f[j + k][0] = (dp[u][j][0] * dp[v][k][1] % Md + f[j + k][0]) % Md;f[j + k][1] = (dp[u][j][1] * dp[v][k][1] % Md + f[j + k][1]) % Md;f[j + k - 1][0] = (dp[u][j][0] * dp[v][k][0] % Md + f[j + k - 1][0]) % Md;f[j + k - 1][1] = ((dp[u][j][1] * dp[v][k][0] % Md + dp[u][j][0] * dp[v][k][1] % Md) % Md + f[j + k - 1][1]) % Md;}}siz[u] += siz[v];for (int j = 1; j <= siz[u]; ++j) for (int k = 0; k <= 1; ++k) {dp[u][j][k] = f[j][k];f[j][k] = 0;}}}; dfs1(1, 0);for (int i = 0; i <= n - 2; ++i) g[i] = 1ll * dp[1][n - i][1] * Pw[n - i - 2] % Md;g[n - 1] = 1;for (int x = 0; x < n; ++x) {for (int j = x; j <= n - 1; ++j) {if ((j - x) & 1) ans[x] = (ans[x] - 1ll * C[j][x] * g[j] % Md) % Md;else ans[x] = (ans[x] + 1ll * C[j][x] * g[j] % Md) % Md;ans[x] = (ans[x] + Md) % Md;}cout << ans[x] << ' ';}return 0;
}