Solution Ⅰ

一道有点有趣的树形 $dp$ + 容斥，反正绕了我半天，这么神仙我也不可能写出来

首先考虑基本思路，直接求解恰好 $k$ 个较难，故考虑先求解大于等于 $k$ 的相似度的方案数，然后再容斥

考虑选定了必选的若干条边后计算方案数。显然此时整个图被分成了若干连通块，假设有 $k$ 个连通块，将连通块缩点，考虑它们可以组成的树的方案数，本来应该是 $k^{k - 2}$，然而对于每个连通块的缩点，它可以向其它连通块中包含的任意一点连接，也就是说，在 purfer 序列中，应当考虑连通块内的点编号在序列中的出现情况，而不是仅仅考虑连通块编号出现在序列中，故 prufer 序列中的每个位置可以填 $n$ 个数，即 $n^{k - 2}$，然而考虑了父亲，还需要考虑儿子，作为叶子节点的缩点后的连通块，同样的里面也是任意点向外连边，故还需乘上 $\prod size_i$，其中，$size_i$ 为连通块 $i$ 的大小，那么综上，对于一个存在 $k$ 个连通块的图，其构造的生成树的方案数为 $n^{k - 2} \times \prod size_i$

那么现在考虑求解 $\prod size_i$，使用树形 $dp$ 求解

令 $f_{root, i, j}$ 表示以 $root$ 为根，总计 $j$ 个连通块，$root$ 所在的连通块大小为 $j$ 的方案数，那么对于 $root$ 的每个儿子有选或不选的两种情况，枚举其儿子 $son$ 的连通块个数 $k$ 及 $son$ 所在连通块大小 $l$：

  • 选：$f_{root, i + k - 1, j + l} += f_{root, i, j} \times f_{son, k, l}$
  • 不选：$f_{root, i + k, j} = f_{root, i, j} \times f_{son, k, l} \times l$

注意每次的 $\times size_i$ 是在整个连通块 $i$ 已经确定下来的时候才能乘，故在其父亲扫描到当前节点的时候才乘上其所在连通块大小

再给出 $g_i = \sum\limits_{i = 1}^n\sum\limits_{j = 1}^{n - i + 1} n^{i - 2}f_{1, i, j} \times j$

注意此时的 $g_k$ 并不是严格意义上的大于等于 $k$ 的相似度的答案，而是对于每一种使用大于等于 $k$ 条重复边分割连通块的方案数，再扩展成树时会重复，故 $g_i - g_{i + 1}$ 并不是 $ans_i$，那么此时再进行容斥，即
$$
g_i = g_i - \sum\limits_{j = i + 1}^{n - 1} g_j\dbinom{j}{i}
$$
即对于每一组恰好 $j$ 条重复边的方案数，那么在每一组方案中选出任意 $i$ 条边即可组成 $g_i$ 中的一种方案，故其方案数的总和即为 $g_i$ 多算的方案数

此时 $g_i$ 即为解

复杂度 $O (n^4)$

复杂度证明

求解 $S = \sum\limits_{i = 1}^n size_i^2 \big(\sum\limits size_{son}^2\big)$ 最大值

现在考虑对于每一个节点 $i$，求解 $size_i^2 \big(\sum\limits size_{son}^2\big)$ 最大值

令 $i$ 的儿子集合为 $SON$，则有 $\sum\limits_{j \in SON} size_j = size_i - 1$，求解 $\sum\limits_{j \in SON} size_j^2$ 最大值

因为 $(size_i - 1)^2 = (\sum\limits_{j \in SON} size_j)^2 \ge \sum\limits_{j \in SON} size_j^2$，故当 $SON$ 大小为 $1$ 时上式取最大值

显然 $S_{max}$ 随着 $n$ 而递增，又由于对于所有 $SON$ 大小为 $1$ 时的点 $i$ 其 $size_i^2 = t_1$，对于其它任意情况点 $i$ 的 $size_i^2 = t_2$，显然可以对这些有标号点找到一种排列使得对于 $\forall i$， 存在 $t_1 \ge t_2$，故这样则可使得 $S$ 取最大值，此时该树为一条链，$S_{max} = \sum\limits_{i = 1}^n i^2 = \frac{(2n +1)n(n + 1)}{6}$，故复杂度上限为 $O (n^4)$

代码

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <cstdio>
#include <cstring>

#define MOD 1000000007

using namespace std;

typedef long long LL;

const int MAXN = 100 + 10;
const int MAXM = 100 + 10;

struct LinkedForwardStar {
	int to;

	int next;
} ;

LinkedForwardStar Link[MAXM << 1];
int Head[MAXN]= {0};
int size = 0;

void Insert (int u, int v) {
	Link[++ size].to = v;
	Link[size].next = Head[u];

	Head[u] = size;
}

int N;

LL power (LL x, int p) {
	p = (p + MOD - 1) % (MOD - 1);
	LL cnt = 1;
	while (p) {
		if (p & 1)
			cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}

LL fact[MAXN]= {0};
LL C (int n, int m) {
	return fact[n] * power (fact[m], MOD - 2) % MOD * power (fact[n - m], MOD - 2) % MOD;
}

LL f[MAXN][MAXN][MAXN]= {0};
int subsize[MAXN]= {0};
LL temp[MAXN][MAXN]= {0};
void DFS (int root, int father) {
	subsize[root] = f[root][1][1] = 1;
	for (int p = Head[root]; p; p = Link[p].next) {
		int v = Link[p].to;
		if (v == father) continue;
		DFS (v, root);
		memset (temp, 0, sizeof (temp));
		for (int i = 1; i <= subsize[root]; i ++)
			for (int j = 1; j <= subsize[root] - i + 1; j ++)
				if (f[root][i][j])
					for (int k = 1; k <= subsize[v]; k ++)
						for (int l = 1; l <= subsize[v] - k + 1; l ++) {
							temp[i + k - 1][j + l] = (temp[i + k - 1][j + l] + f[root][i][j] * f[v][k][l] % MOD) % MOD; // select
							temp[i + k][j] = (temp[i + k][j] + f[root][i][j] * f[v][k][l] % MOD * l % MOD) % MOD; // do not select
						}
		memcpy (f[root], temp, sizeof (f[root]));
		subsize[root] += subsize[v];
	}
}

LL g[MAXN]= {0};

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}
void output (LL x) {
	if (x >= 10) output (x / 10);
	putchar (x % 10 + '0');
}

int main () {
	N = getnum ();
	for (int i = 1; i < N; i ++) {
		int u = getnum (), v = getnum ();
		Insert (u, v), Insert (v, u);
	}
	DFS (1, 0);
	// 相似度 n - k
	for (int i = 1; i <= N; i ++) {
		LL base = power (1ll * N, i - 2);
		for (int j = 1; j <= N - i + 1; j ++) {
			g[N - i] = (g[N - i] + base * f[1][i][j] % MOD * j % MOD) % MOD;
			if (N - i == 1)
				cout << "Test: " << f[1][i][j] % MOD % MOD << endl;
		}
	}
	fact[0] = 1;
	for (int i = 1; i <= N; i ++) fact[i] = fact[i - 1] * i % MOD;
	for (int i = N - 1; i >= 0; i --)
		for (int j = i + 1; j < N; j ++)
			g[i] = (g[i] - g[j] * C (j, i) % MOD + MOD) % MOD;
	for (int i = 0; i < N; i ++) {
		if (i > 0) putchar (' ');
		output (g[i]);
	}
	puts ("");

	return 0;
}

/*
3
1 2
1 3
*/

/*
4
1 2
2 3
3 4
*/

/*
4
1 2
1 3
1 4
*/

Solution Ⅱ

这是一个矩阵树定理的解法

这与「[北京省选集训2019]生成树计数」极为相似，都是多项式矩阵树定理

对于不在给定树上的边将其权值赋为 $1$，对于在给定树上的边将其权值赋为 $x$（即多项式 $x$），然后矩阵树定理即可