Prufer 序列学习笔记

· · 题解

一、前言

主要是用于计数问题。

前置知识：树的定义。

二、定义

对于一棵有 n 个节点的无根树 T，定义其 Prufer 序列为执行以下操作 n-2 次所形成的长度为 n-2 的正整数序列。

  1. 选择其编号最小的度数为 1 的节点，输出唯一与其相邻的节点的编号。

  2. 删除这个节点以及以其为端点的唯一边。

然后这个东西有一些性质：

  1. 容易知道最后树上一定是只留下 2 个度数为 1 的节点以及连着它们的边，其中一个编号为 n。

证明：将无根树视作以 n 为根的有根树，容易知道由于树没有环，所以当点的个数 >1 时叶子结点的个数 \ge 2。如果树上节点个数 >1，存在一个叶子节点 y\ne n，删除节点 y，一定比删除节点 n 更优。□

  1. 这个东西可以与一棵有编号的无根树一一对应。

这个性质可以通过给出一种一一对应的映射方式来证明，详见下文。

  1. 每个节点在 Prufer 序列里出现的次数是它在无根树上的度数减一，特别地，一开始的所有叶子节点不会出现在 Prufer 序列里。

证明：每往 Prufer 序列中加一个节点，就会删掉一条边。最后每个节点都至多只有一条边。我们知道因为每次删的都是叶子节点，所以每删去一个节点以及以其为端点的唯一边后，无根树仍连通。具体来说，如果我们将树视为以 n 为根的有根树，最后剩下的 2 个节点中一定有根 n，而且另外一个是 n 的一个子节点。而且容易知道一个节点 x 的所有子节点被删时，标在 Prufer 序列里的数都是 x，而一个节点 y 被删时，表在 Prufer 序列里的数是它的父亲节点的编号。那么除了 n 以外每个节点的子节点都被删光了，所以每个节点都被标了它的子节点的个数次，所以是 d_i-1 次。而对于节点 n，它的子节点个数是 d_i，它有一个儿子没被删，所以它也被标了 d_i-1 次。□

三、用途

  1. 可以知道有 n 个节点的不同有标号无根树一共有 n^{n-2} 棵，即有 n 个点的完全图的不同生成树一共有 n^{n-2} 棵（Cayley 定理）。这是因为它的长为 n-2 的 Prufer 序列的每一位都可以填 1 到 n 的任意正整数。有 n 个节点的不同有标号有根树一共有 n^{n-1} 棵，因为处理出无根树之后，n 个点都可以做根。

  2. 可以知道有 n 个节点，其中编号为 i 的节点的度数为 d_i，并且满足 \sum\limits_{i=1}\limits^n{d_i}=2\times n-2 的不同有标号无根树有 \frac{(n-2)!}{\prod\limits_{i=1}\limits^n{(d_i-1)!}} 个。注意分母是先做阶乘再连乘。这是因为这棵无根树的 Prufer 序列可看作 d_1-1 个 1、d_2-1 个 2、……、d_n-1 个 n 所组成的，长度为 n-2 的可重复元素的全排列。

四、例题

例 1.P6086 【模板】Prufer 序列

这一题是要实现 O(n) 的 Prufer 序列和有标号无根树的互相转换。 出于方便考虑，将无根树视作以 n 为根的有根树（事实上，根据定义，这不影响结果，而且只是为了在表述上更方便大家理解），于是下面将所有节点往 n 号节点方向非自身的最近点称为其父亲节点。

O(n\log n) 做法

首先实现父亲序列转 Prufer。一个明显的想法是记录所有点的子节点个数，维护一个小根堆（优先队列），把所有子节点个数为 0 的点扔进这个小根堆。然后每次取队头出队，然后删掉它，并且将它的父亲节点的度数减一，然后记录在 Prufer 序列里。接下来检查它父亲节点的子节点个数，如果降为 0 就入队。然后我们就求出了 Prufer 序列。时间复杂度 O(n\log n)，且常数较大。

然后就是 Prufer 序列转父亲序列，还是找出每一个节点的子节点数数（即在序列中出现的次数），然后找到所有子节点数为 0 的点，加入优先队列。每次取出队头，然后删掉它，并且我们可以知道第 i 次出队的点的父亲的编号实际上就是 Prufer 序列里第 i 个数，然后将其父亲节点的度数减一。最后就可以找到 n-2 个节点的父亲节点，然后 n 没有父亲节点，然后剩下一个节点的父亲节点为 n，然后我们就求出了父亲序列。时间复杂度 O(n\log n)，且常数较大。

所以就可以实现在 O(n\log n) 的时间内互相转换，同时也证明了 Prufer 序列与一棵有标号无根树一一对应。所以以上所说的所有计数问题成立。

int main(){
    n=read();m=read();
    if(m==1){
        for(int i=1;i<=n-1;i++)d[f[i]=read()]++;
        for(int i=1;i<=n;i++)if(!d[i])q.push(i);
        for(int i=1;i<=n-2;i++){
            p[i]=f[q.top()];q.pop();
            if(!--d[p[i]])q.push(p[i]);
        }
        for(int i=1;i<=n-2;i++)ans^=1ll*i*p[i];
    }else{
        for(int i=1;i<=n-2;i++)d[p[i]=read()]++;
        for(int i=1;i<=n-1;i++)f[i]=n;
        for(int i=1;i<=n;i++)if(!d[i])q.push(i);
        for(int i=1;i<=n-2;i++){
            f[q.top()]=p[i];q.pop();
            if(!--d[p[i]])q.push(p[i]);
        }
        for(int i=1;i<=n-1;i++)ans^=1ll*i*f[i];
    }
    cout<<ans<<'\n';
    return 0;
}

AC 记录，通过了就很神奇，直接 O(n\log n) 过 5000000 是吧。

O(n) 做法

但是这一题的正解是 O(n) 的。

我们可以发现，这一次删了一个点，那么下一次删哪个点。首先，有可能是原本就是度数为 1 的节点。其次，它还有可能是当前节点的父亲节点。

所以我们可以维护一个指针，初始时为 1，然后每次遇到一个节点 y，如果它的子节点被删光，那么就把它的父亲节点 x 记录进 Prufer 序列里，然后把 x 的残存的子节点数减一，如果 x 的子节点数因此变为 0，分类讨论：如果 x>y，则不用管它，继续自增指针；如果 x<y，那么要另外处理 x，删除它，继续记录 x 的父亲节点，然后继续判断……直到这个连锁反应停止为止。因为每个节点只会处理 1 次，所以时间复杂度 O(n)。

把 Prufer 序列转换成父亲序列同理。

int main(){
    n=read();m=read();
    if(m==1){
        for(int i=1;i<=n-1;i++)d[f[i]=read()]++;
        for(int i=1,j=1,x;i<=n-2;i++,j++){
            while(d[j])j++;p[i]=f[x=j];
            while(i<=n-2&&!--d[p[i]]&&p[i]<j)p[++i]=f[x=f[x]];
        }
        for(int i=1;i<=n-2;i++)ans^=1ll*i*p[i];
    }else{
        for(int i=1;i<=n-2;i++)d[p[i]=read()]++;p[n-1]=n;
        for(int i=1,j=1,x;i<=n-1;i++,j++){
            while(d[j])j++;f[x=j]=p[i];
            while(i<=n-1&&!--d[p[i]]&&p[i]<j)f[x=f[x]]=p[++i];
        }
        for(int i=1;i<=n-1;i++)ans^=1ll*i*f[i];
    }
    cout<<ans<<'\n';
    return 0;
}

AC 记录

然后这个东西有什么用呢？基本没用，毕竟现有的大部分 OI 题只考计数，不考求 Prufer 序列。但是万一考了呢？学有余力的话还是学一学吧。

例 2.P4981 父子

这一题就是求一个有 n 个点的完全图的生成树有几个。输出 n^{n-2} 即可。

例 3.P4430 小猴打架

这一题就是求一个有 n 个点的完全图的生成树的边共能形成多少种不同的排列。 注意到两棵不同的生成树至少有一个点不同，所以边形成的排列一定不同，所以答案就是生成树的棵数乘上树的边数的全排列的方法数，即 n^{n-2}\times (n-1)!。

例 4.P2290 [HNOI2004]树的计数

使用上面（“用途”中）所讲的公式，可以知道是 \frac{(n-2)!}{\prod\limits_{i=1}\limits^n{(d_i-1)!}}。注意特判 \sum\limits_{i=1}\limits^n{d_i}\ne 2\times n-2 的情况（此时组不成一棵树，应该输出 0）以及图不连通的情况。

例 5.P2624 [HNOI2008]明明的烦恼

考虑 Prufer 序列。令 s=\sum\limits_{d_i>0}^n{(d_i-1)}，k=\sum\limits_{d_i>0}^n{1}，q_i 代表第 i 个满足 d_r>0 的 r，那么我们知道 Prufer 序列里面有 s 个数是固定的，分别是 d_{q_i}-1 个 q_i，以及 Prufer 序列中剩下 n-2-s 个数，每一个数都可以是节点编号中的剩下 n-k 个数的任何一个。所以答案就是所有 d_{q_i}-1 个 q_i 的可重全排列乘上 n-2 个位置中选 s 个方案数乘上 n-k 的 n-2-s 次方，即 \frac{s!}{\prod\limits_{d_i>0}\limits^n{(d_i-1)!}}\times C_{n-2}^s\times (n-k)^{n-2-s}。要实现高精度乘除。