浅谈 Prüfer 序列

Prüfer 序列的定义

Prüfer 序列常用于组合计数。

板子题：P6086 【模板】Prüfer 序列

Prüfer 序列可以将一个带标号的 $n$ 个节点的数用 $[1,n]$ 中的 $n-2$ 个整数表示

或者可以认为 Prüfer 序列是「完全图的生成树」与「数列」的双射。

注意，Prüfer 序列的长度为 $n-2$ ！

例如，下图的带标号无根树的 Prüfer 序列为 $\{4,4,4,5\}$ 。

Prüfer 序列与无根树的相互转化

无根树的 Prüfer 序列的构造方法如下：

每次选择一个编号最小的叶子节点并删除它，然后记录它连接到的那个节点
重复 $n-2$ 次后就只剩下两个节点，算法结束。

其实这个过程就是把外面一层一层的删掉，最后剩下两个节点

我们可以用一个指针 $p$ 来寻找维护「编号最小的叶子节点」

具体地，我们可以先把无根树随便找个节点 $\mathtt{dfs}$ 后转成有根树

注：板子题里直接默认 $n$ 为转化后的根节点，并给出了每个节点的父亲。（挺良心的）

我们先找到原树「编号最小的叶子节点」，记为 $u$ ，并记它的父节点为 $v$ 。

然后我们删除 $u$ 。

如果 $v$ 成为了新的叶子节点，且 $v$ 编号比 $u$ 小，则直接继续删除。
否则，自增 $p$ 来寻找下一个编号最小的叶节点。

时间复杂度 $O(n)$ ，代码：

void t2p() // tree to prüfer
{
    // f[i]为i的父节点， d[i]为i的度数， p[i]为prüfer序列
    // 题目默认了转化后的根为n 
    for(int i=1; i<n; i++) { read(f[i]); ++d[f[i]]; }
    for(int i=1,j=1; i<=n-2; i++,j++)
    {
        while(d[j]) ++j; p[i]=f[j];
        while(i <= n-2 && !(--d[p[i]]) && p[i] < j) p[i+1]=f[p[i]],++i;
    }
    for(int i=1; i<=n-2; i++) ans ^= i * p[i]; // 题目要求这么输出的。
}

Prüfer 序列构造无根树的方法

每次我们选择一个编号最小且度数为 $1$ 的节点
与当前枚举到的 Prüfer 序列的点连接，然后同时减掉两个点的度数。

重复 $n-2$ 次之后就只剩下两个度数为 $1$ 的节点

然后我们把剩下的两个点连一条边就好了

时间复杂度 $O(n)$ ，代码：

void p2t() // prüfer to tree
{
    // f[i]为i的父节点， d[i]为i的度数， p[i]为prüfer序列
    for(int i=1; i<=n-2; i++) { read(p[i]); ++ d[p[i]]; }
    p[n-1]=n; // 题目默认了转化后的根为n 
    for(int i=1,j=1; i<n; i++,j++)
    {
        while(d[j]) ++j; f[j]=p[i];
        while(i < n && !(--d[p[i]]) && p[i] < j) f[p[i]] = p[i+1], ++i;
    }
    for(int i=1; i<n; i++) ans ^= i*f[i]; // 题目要求这么输出的。
}