0. 前言

邦邦卡邦！又学会了新的双射方式！这次是关于树的双射内容！

1. 定义与构建

1.1 定义

prufer 序列，又叫做 prüfer 序列，因为键盘平时不太好打出来 ü 所以一般叫做 prufer 序列。他的作用就是可以将一个有标号的nn 个点的树映射成一个由n−2n-2 个在[1,n][1,n] 范围内的数所组成的序列，同时这个序列也会唯一对应一个树。也就是说，prufer 序列和树结构构成双射。

1.2 构建

钦定nn 为树的根节点，因为这个树我没有说这是有根树，所以不会影响。

每次选择编号最小的叶子结点并删掉它，再把它的父亲的编号加入序列中。重复此操作，直到树上只有两个点为止。显然，这两个点中必有一个是编号最大的点 nn。为什么是两个点呢？假设我们再进行一次操作，那么进入序列的必然是 nn。这是没有意义的操作。而如果我们进行了这次操作，末尾不为 nn 的 prufer 序列将失去对应一个树的优秀性质。

以下是一个n=7n=7 的例子：

最终的序列就是{2,2,3,3,2}\{2,2,3,3,2\}。

1.3 还原

那么可以看得出来，经过此操作，每个树都对应了一个 prufer 序列。如果我么能从 prufer 序列还原出树，那么就证明了树和 prufer 序列是一一对应的。

prufer 序列有一个性质如下：

  • 树上每个点的度数等于在 prufer 序列上出现的次数加11。

这个性质很好想，因为度数要么来自儿子要么来自父亲贡献，没删掉一个儿子，这个点就会在 prufer 序列上出现一次。而众所周知的是树上一个节点有且仅有一个父亲，所以出现次数加11 就是度数。而对于根节点为nn 则不一样，它在 prufer 序列中出现的次数为它的儿子数减11，即它的度数减11。

有了这个性质，我们就可以得知没有出现在 prüfer 序列上的点，一定是叶子结点。

这样我们轻易就能得到树上最小的叶子结点的编号，就是没有在 prüfer 序列上出现的点。我们将这个叶子结点与 prüfer 序列上的第一个数连边，然后删除这个点和 prüfer 序列上的第一个数。如果将编号大于该叶子结点的编号减一，我们就得到了一个长度为n−3n-3 的 prüfer 序列，对应一个大小为 n−1n-1 的树。因此可以使用同样的方法重复操作，再把最后剩下的点连向 nn，就可以得到原树。

以下为{2,2,3,3,2}\{2,2,3,3,2\} 的构造：

  • 度数：dg[1,7]={1,4,3,1,1,1,1}dg[1,7]=\{1,4,3,1,1,1,1\}。
  • 取出11，令1→21\to 2，dg[1,7]={0,3,3,1,1,1,1}dg[1,7]=\{0,3,3,1,1,1,1\}。
  • 取出44，令4→24\to 2，dg[1,7]={0,2,3,0,1,1,1}dg[1,7]=\{0,2,3,0,1,1,1\}。
  • 取出55，令5→35\to 3，dg[1,7]={0,2,2,0,0,1,1}dg[1,7]=\{0,2,2,0,0,1,1\}。
  • 取出66，令6→36\to 3，dg[1,7]={0,2,1,0,0,0,1}dg[1,7]=\{0,2,1,0,0,0,1\}。
  • 取出33，令3→23\to 2，dg[1,7]={0,1,0,0,0,0,1}dg[1,7]=\{0,1,0,0,0,0,1\}。
  • prufer 序列遍历完，还剩下n=7n=7 和22 号点，连接即可。

总连边：

1
2
3
4
5
6
1 2
4 2
5 3
6 3
3 2
7 2

可以自行验证，有结果：

故证明成立。

1.4 线性时间做到构造与还原

显然可以使用堆做到O(nlog⁡n)O(n\log n) 的复杂度，但其实有更优的做法。

维护一个下标pp，初始值为最小的叶结点编号。重复以下操作：

  1. 删除编号为pp 的结点，并检查是否使其父亲成为叶结点。
  2. 设其父亲的编号为xx。先将xx 加入序列。若xx 成为了新的叶子结点，判断其与pp 的大小关系。若x<px<p，则立即删除xx，然后重复判断xx 的父亲；否则不管。
  3. 使pp 自增，直到pp 指向一个叶子结点为止。

因为每条边最多被访问一次（在删点的时候访问父亲），指针最多遍历每个点一次，所以复杂度是O(n)O(n) 的。

这有点像可删堆的操作，可以结合理解。

对于还原类似，用同样的方法寻找编号最小的叶结点删除即可。

以下为 P6086 【模板】Prüfer 序列 的代码：

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=5e6+15;
int fa[MN],dg[MN],p[MN],n,m,ans;

void TtoP(){
    for(int i=1;i<n;i++){
        cin>>fa[i];
        dg[fa[i]]++;
    }
    for(int i=1,x,j=1;i<=n-2;i++,j++){
        while(dg[j]) j++;
        p[i]=fa[x=j];
        while(i<=n-2&&!--dg[p[i]]&&p[i]<j){
            p[++i]=fa[x=fa[x]];
        }
    }
    for(int i=1;i<=n-2;i++){
        ans^=1ll*i*p[i];
    }
}

void PtoT(){
    for(int i=1;i<=n-2;i++){
        cin>>p[i];
        dg[p[i]]++;
        p[n-1]=n;
    }
    for(int i=1,x,j=1;i<=n-1;i++,j++){
        while(dg[j]) j++;
        fa[x=j]=p[i];
        while(i<=n-1&&!--dg[p[i]]&&p[i]<j) fa[x=fa[x]]=p[++i];
    }
    for(int i=1;i<=n-1;i++){
        ans^=1ll*i*fa[i];
    }
}

signed main(){
    cin>>n>>m;
    if(m==1){
        TtoP();
    }else PtoT();
    cout<<ans;
    return 0;
}

1.5 性质总结

说了这么多，我们来总结几个关键的性质来辅助做题。

  • Prufer 序列与树构成唯一双射，在计数问题中对一般树计数可以考虑直接对 prufer 序列计数。
  • 树上每个点的度数等于在 prufer 序列上出现的次数加11。
  • 所有没在序列里出现过的点，一定是树中的叶子。
  • 对于完全图KnK_{n} 有nn−2n^{n-2} 颗生成树。（任意一个长度为n−2n-2 的值域[1,n][1,n] 的序列计数）

我们对第四个结论进行推广：

  • nn 个点形成有kk 颗树的有标号无根树森林，使得给定的kk 个点两两不属于同一棵树，此时的方案总数为 k⋅nn−k−1k\cdot n^{n-k-1}。
  • 指定点度数的生成树方案为(n−2)!∏i=1n(di−1)\dfrac{(n-2)!}{\prod_{i=1}^n (d_{i}-1)}。
  • 若nn 个点已经被连成大小为{si}i=1k\{s_{i}\}_{i=1}^k 的kk 个连通块，则在这些连通块之间加边构成生成树的方案数为nk−2∏i=1ksin^{k-2}\prod_{i=1}^k s_{i}。

推广 1 的证明：给定nn 个点和kk 个指定点，两两不在同一棵树的无根森林数：

  • 每个指定点作为不同树的根，有根森林数n n−kn^{\,n-k}。
  • 无根森林对应有根森林，每棵树根可选择kk 种，调整得到：

k⋅n n−k−1.k \cdot n^{\,n-k-1}.

推广 2 的证明：指定nn 点度数{di}\{d_i\} 的生成树数：

  • Prüfer 序列长度n−2n-2。
  • 每点viv_i 出现di−1d_i-1 次。
  • 多重排列计数：

(n−2)!∏i=1n(di−1)!.\frac{(n-2)!}{\prod_{i=1}^n (d_i-1)!}.

推广 3 在后面例题会证明。

2. 例题

推广 2 P2290

显然。

推广 3 CF156D Clues

设sis_{i} 为第ii 个连通块的点数，did_{i} 表示连通块在树上的度数。

那么有 Prufer 序列方案数：

(k−2)!(d1−1)!(d2−1)!…(dn−1)!\dfrac{(k-2)!}{(d_{1}-1)!(d_{2}-1)!\dots (d_{n}-1)!}

而一个连通块连接边的方案为∏i=1ksidi\prod_{i=1}^k s_{i}^{d_{i}}。那么总方案数枚举did_{i}乘起来即为：

∑di>1,∑i=1kdi=2k−2(k−2)!(d1−1)!(d2−1)!…(dn−1)!∏i=1ksidi\sum\limits_{d_{i}>1,\sum\limits_{i=1}^k d_{i}=2k-2}\dfrac{(k-2)!}{(d_{1}-1)!(d_{2}-1)!\dots (d_{n}-1)!} \prod_{i=1}^k s_{i}^{d_{i}}

设ei=di−1e_{i}=d_{i}-1，有

∑ei>0,∑i=1kei=k−2(k−2)!e1!e2!…ek!∏i=1ksiei+1\sum\limits_{e_{i}>0,\sum\limits_{i=1}^k e_{i}=k-2}\dfrac{(k-2)!}{e_{1}!e_{2}!\dots e_{k}!} \prod_{i=1}^k s_{i}^{e_{i}+1}

考虑多元二项式定理：

(x1+⋯+xm)p=∑ci≥0,∑i=1mci=p(pc1,c2,⋯ ,cm)⋅∏i=1mxici(x_1 + \dots + x_m)^p = \sum_{c_i \ge 0,\sum_{i=1}^m c_i = p}\binom{p}{c_1, c_2, \cdots ,c_m}\cdot \prod_{i=1}^m{x_i}^{c_i}

原式变为：

(s1+s2+⋯+sk)k−2⋅∏i=1ksi(s_1+s_2+\cdots+s_k)^{k-2}\cdot\prod_{i=1}^ks_i

即：

nk−2⋅∏i=1ksin^{k-2}\cdot\prod_{i=1}^ks_i

P2624 [HNOI2008] 明明的烦恼

只给了一些点的度数，对于给定度数点的排列方案数也是可以算出来的，记sum=∑i=1n(di−1)sum=\sum\limits_{i=1}^n (d_{i}-1)，令cntcnt 表示已知度数的点的个数。那么由上述推论 2 有：

(n−2sum)×sum!∏i=1cnt(di−1)\binom{n-2}{sum}\times \frac{sum!}{\prod_{i=1}^{cnt} (d_{i}-1)}

然后剩下的n−cntn-cnt 个数任意插在(n−sum−2)(n-sum-2) 的位置上即可，即(n−cnt)n−sum−2(n-cnt)^{n-sum-2}。答案就是乘起来即可，但是不给模数是有什么心事吗？我直接 python 喵了。

CF917D Stranger Trees

等会，题面这个图还有题目背景，莫非是？

咳咳，回到正题，首先看到 “恰好” 直接哈气。用二项式反演反演成至少，有：gk=∑i=kn(ik)fi⇔fk=∑i=kn(−1)i−k(ik)gig_{k}=\sum\limits_{i=k} ^n \binom{i}{k} f_{i} \Leftrightarrow f_{k}=\sum\limits_{i=k}^n (-1)^{i-k} \binom{i}{k} g_{i}。其中ff 为答案，gg 为至少kk 条边相同的方案数。

然后考虑gg 怎么算，发现这玩意我们把钦定的ii 条边断开，会形成n−in-i 个连通块，而这些连通块都是独立树计数的。根据 Prufer 定理有任意连边方案数：

nm−2∏i=1msin^{m-2}\prod_{i=1}^m s_{i}

mm 为连通块个数，其中sis_{i} 还是连通块大小。

然后考虑如何快速计算，发现如果直接做因为边不确定状压直接爆炸。数据范围O(n3)O(n^3)，考虑发掘性质。

我们考虑把gkg_{k} 的组合意义拆分，前式子可以随便计算，而后面却要求我们快速不用状压计算。考虑 DP，设f(i,j,k)f(i,j,k) 表示ii 子树内，分成了jj 个连通块，当前ii 所在连通块大小为kk 的方案数。时间复杂度O(n3)O(n^3) 可以O(1)O(1) 转移但是我认为是O(n4)→O(n5)O(n^4)\to O(n^5) 就很难泵。

但是我们显然有更好的做法，考虑我们只是在计算∏i=1msi\prod_{i=1}^m s_{i}，考虑复杂度瓶颈就是在于这个kk 这一维度让我们的优化没有前途。考虑切换组合意义，发现∏i=1msi\prod_{i=1}^m s_{i} 的本质就是给每个连通块内部任意定根的方案数，把根是否确定放进状态中即可。

那么这很好考虑设f(i,j,0/1)f(i,j,0/1) 表示ii 子树内，分成了jj 个连通块，ii 所在连通块是否定根的方案数，转移用背包对子树合并即可，时间复杂度O(n2)O(n^2)。