浅谈 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]; // 题目要求这么输出的。
}