Prufer 序列
Prufer 序列可以将一个带标号 \(n\) 个结点的树用 \([1, n]\) 中的 \(n - 2\) 个整数表示，也可以理解为完全图的生成树与数列之间的双射。
建立过程：每次选择编号最小的叶子节点并删掉，然后在序列中记录它连接的节点标号，重复 \(n - 2\) 次后结束。
不难发现：
- 构造完 Prufer 序列后原树中肯定会剩下两个节点，其中必然有一个节点为 \(n\) 。
- 因为一棵无根树至少有两个叶子节点，\(n\) 肯定不会成为编号最小的叶子节点，故不可能被删去。
- 每个节点在序列中出现的次数就是其度数 \(-1\) 。
- 每个节点在被删除前其度数 \(-1\) 个叶子节点一定被删完，序列中就会出现度数 \(-1\) 次其编号。
为了方便，规定树的根为 \(n\) ，因为 \(n\) 一定不会被删掉。
线性建立 Prufer 序列
考虑维护一个指向编号最小的叶子节点的指针 \(p\) 初值为 \(1\) 。同时我们维护每个节点的度数以维护新产生的叶子节点。过程如下：
- 删除 \(p\) 指向的节点，更新 Prufer 序列。
- 若删去 \(p\) 后其父亲为新的叶子节点且编号 \(< p\) ，立即删除这个节点。重复此操作直到不满足条件。
- 让 \(p\) 自增直到 \(p\) 指向一个未被删除的叶子节点，跳转至步骤一。
每个点在遍历指针时最多被访问一次，每条边在更新度数时最多被删除一次，因此时间复杂度时 \(O(n)\) 的。
inline void BuildPrufer() {
for (int i = 1; i < n; ++i)
++deg[fa[i]], ++deg[i];
for (int cur = 1, tot = 0; tot < n - 2; ++cur) {
while (deg[cur] > 1)
++cur;
--deg[prufer[++tot] = fa[cur]];
while (tot < n - 2 && deg[prufer[tot]] == 1 && prufer[tot] < cur)
++tot, --deg[prufer[tot] = fa[prufer[tot - 1]]];
}
}
线性重建树
由 Prufer 序列，可以得到原树上每个节点的度数和最小的叶子节点编号，这个节点肯定和 Prufer 序列的第一个数连接。
类似的，我们同样维护一个指针 \(p\) ，重建过程中同样会不断产生新的叶子节点，再连边即可。
inline void BuildTree() {
fill(deg + 1, deg + 1 + n, 1);
for (int i = 1; i <= n - 2; ++i)
++deg[prufer[i]];
for (int cur = 1, tot = 0; tot < n - 2; ++cur) {
while (deg[cur] > 1)
++cur;
--deg[fa[cur] = prufer[++tot]];
while (tot < n - 2 && deg[prufer[tot]] == 1 && prufer[tot] < cur)
++tot, --deg[fa[prufer[tot - 1]] = prufer[tot]];
}
fa[prufer[n - 2]] = n;
}
Cayley 公式
\(n\) 个点组成的无向完全图有 \(n^{n - 2}\) 棵生成树。使用 Prufer 序列可以很简单地证明。
图连通方案数
一个 \(n\) 个点 \(m\) 条边的带标号无向图有 \(k\) 个连通块，添加 $ k - 1$ 条边使得整个图连通，求方案数。
建立新图并将每个联通块视为点 \(A_{1 \sim k}\) ，令 \(s_i\) 为每个连通块中点的数量， \(d_i\) 为 \(A_i\) 的度数（不是连通块内部的度数）
因为度数和为边数的两倍，所以有 \(\sum_{i = 1}^k d_i = 2k - 2\) 。
由于 Prufer 序列中每个节点出现的次数就是其度数 \(-1\) ，所以对于给定的序列 \(d\) 在新图中的 Prufer 序列的方案数为：
\[\dbinom{k - 2}{d_1 - 1, d_2 - 1, \cdots, d_k - 1} = \cfrac{(k - 2)!}{(d_1 - 1)! (d_2 - 1)! \cdots (d_k - 1)!} \]对于第 \(i\) 个连通块，它有 \(s_i^{d_i}\) 种连接方式，因此对于给定 \(d\) 序列使图联通的方案数是：
\[\dbinom{k - 2}{d_1 - 1, d_2 - 1, \cdots, d_k - 1} \cdot \prod_{i = 1}^k s_i^{d_i} \]枚举所有的 \(d\) 序列，总方案数即为：
\[\sum_{d_i \geq 1, \sum_{i = 1}^k d_i = 2k - 2} \dbinom{k - 2}{d_1 - 1, d_2 - 1, \cdots, d_k - 1} \cdot \prod_{i = 1}^k s_i^{d_i} \]有多元二项式定理：
\[(x_1 + \cdots + x_m)^p = \sum_{c_i \geq 0, \sum_{i = 1}^m c_i = p} \dbinom{p}{c_1, c_2, \cdots, c_m} \cdot \prod_{i = 1}^m x_i^{c_i} \]尝试对原式换元，令 \(e_i = d_i - 1\) ，显然 \(\sum_{i = 1}^k e_i = k - 2\) ，于是原式转化为：
\[\begin{aligned} & \ \sum_{e_i \geq 0, \sum_{i = 1}^k e_i = k - 2} \dbinom{k - 2}{e_1, e_2, \cdots, e_k} \cdot \prod_{i = 1}^k s_i^{e_i + 1} \\ =& \ (s_1 + s_2 + \cdots + s_k)^{k - 2} \cdot \prod_{i = 1}^k s_i \\ =& \ n^{k -2} \cdot \prod_{i = 1}^k s_i \end{aligned} \]应用
\[\dbinom{k - 2}{d_1 - 1, d_2 - 1, \cdots, d_k - 1} = \cfrac{(k - 2)!}{(d_1 - 1)! (d_2 - 1)! \cdots (d_k - 1)!} \]给出每个点的度数，求满足条件的树的方案数。
\(n \leq 150\)
直接求会炸，注意到其等价于：
\[\prod_{i = 1}^{k} \dbinom{\sum_{j = i}^k (d_i - 1)}{d_i - 1} \]#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1.5e2 + 7;
ll C[N][N];
int deg[N];
int n, sum;
signed main() {
scanf("%d", &n);
if (n == 1) {
scanf("%d", deg + 1);
putchar(deg[1] ? '0' : '1');
return 0;
}
for (int i = 1; i <= n; ++i) {
scanf("%d", deg + i);
sum += deg[i] - 1;
if (!deg[i])
return putchar('0'), 0;
}
if (sum != n - 2)
return putchar('0'), 0;
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] + C[i - 1][j - 1];
}
ll ans = 1;
for (int i = 1; i <= n; ++i)
ans *= C[sum][deg[i] - 1], sum -= deg[i] - 1;
printf("%lld", ans);
return 0;
}
给出一个 \(k\) 次多项式 \(F(x) \bmod 59393\) ，构造一棵 \(n\) 个点的树，记 \(d_i\) 为每个点的度数，求 \(\max \sum_{i = 1}^n F(d_i)\) ，输出这个最大值并给出一组方案。
\(n \leq 3000, k \leq 10\)
不难发现求出一组 \(d_i\) 后即可用 Prufer 序列重建树即可。
先给每个节点分配 \(1\) 的度数，于是总度数和变为 \(n - 2\) 。
设 \(f_i\) 表示 Prufer 序列中分配完 \(i\) 位可获得的最大权值和，有：
\[f_j = \max (f_{j - i + 1} + F(i) - F(1)) \\ f_0 = n \times F(1) \]#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int Mod = 59393;
const int N = 3e3 + 7, K = 1e1 + 7;
int prufer[N], deg[N], fa[N];
int a[K], w[N], f[N], g[N];
int n, k;
inline void prework() {
for (int i = 0; i <= n; ++i)
for (int j = k; ~j; --j)
w[i] = (w[i] * i % Mod + a[j]) % Mod;
}
inline void BuildTree() {
fill(deg + 1, deg + 1 + n, 1);
for (int i = 1; i <= n - 2; ++i)
++deg[prufer[i]];
for (int cur = 1, tot = 0; tot < n - 2; ++cur) {
while (deg[cur] > 1)
++cur;
--deg[fa[cur] = prufer[++tot]];
while (tot < n - 2 && deg[prufer[tot]] == 1 && prufer[tot] < cur)
++tot, --deg[fa[prufer[tot - 1]] = prufer[tot]];
}
fa[prufer[n - 2]] = n;
}
signed main() {
scanf("%d%d", &n, &k);
for (int i = 0; i <= k; ++i)
scanf("%d", a + i);
prework();
printf("%d ", n - 1);
if (n == 1)
return printf("%d", w[0]), 0;
else if (n == 2)
return printf("%d\n1 2", w[1]), 0;
f[0] = n * w[1];
for (int i = 2; i <= n; ++i)
for (int j = i - 1; j <= n - 2; ++j)
if (f[j - i + 1] + w[i] - w[1] > f[j])
f[j] = f[j - i + 1] + w[i] - w[1], g[j] = j - i + 1;
printf("%d\n", f[n - 2]);
for (int i = n - 2, tot = 0, cur = 1; i; i = g[i], ++cur)
for (int j = 1; j <= i - g[i]; ++j)
prufer[++tot] = cur;
BuildTree();
for (int i = 1; i < n; ++i)
printf("%d %d\n", i, fa[i]);
return 0;
}