Prufer序列（无根树与序列的互相转化及其性质）

什么是Prufer序列？

Prufer序列是将一个带有节点编号的无根树转化为一个序列的过程，且每一个无根树唯一的确定一个prufer序列。反过来也成立。

Prufer序列的性质

原树中顶点 $v$ 的度数 $- 1 =$ 序列中顶点v的出现次数
n个顶点的无根树的Prufer序列的长度为n-2
一个Prufer序列与一个无根树一一对应

将无根树转化为Prufer序列

方法：

一棵树要得到普吕弗序列，方法是逐次去掉树的顶点，直到剩下两个顶点。考虑树T，其顶点为{1, 2, …, n}。在第i步，去掉标号最小的叶，并把普吕弗序列的第i项设为这叶的邻顶点的标号。

一棵树的序列明显是唯一的，而且长为n − 2。

算法：

使用的数据结构：维护一个度数为1的set集合即可.

初始度数为1的集合（所有叶子）.
每次从度数为1的叶子顶点集合中找到编号最小的顶点u，并将其从度数为1的集合中删去。将u连接的顶点v加入prufer序列，删除u连接的所有边。
更新u和v的度数，v的度数为1则加入度数为1的集合。
当加入序列的数的个数为n-2时候停止。否则返回到第二步。

具体实现：

时间复杂度为O(nlogn)。代码经过自己的部分测试是正确的，若有人发现bug请在评论区指出，我将尽快进行修改

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=1e5+10;
vector<int> prufer;
vector<int> g[N];
int du[N];
/* 输入:顶点个数n和树g[] 输出:prufer序列 */
void TreeToPrufer(int n,vector<int> g[])//g[]中存储的是无向边,共有n个顶点
{
    set<int> leaf;
    mset(du,0);
    prufer.clear();
    for(int u=1;u<=n;++u)
        for(int v:g[u]) du[v]++;
    for(int i=1;i<=n;++i) if(du[i]==1) leaf.insert(i);
    while(prufer.size()!=n-2)
    {
        int u=*leaf.begin();
        du[u]=0;
        leaf.erase(leaf.begin());
        for(int v:g[u])
        {
            if(!du[v]) continue;
            prufer.push_back(v);
            du[v]--;
            if(du[v]==1) leaf.insert(v);
        }
    }
    printf("following is prufer sequence of tree:\n");
    for(int v:prufer) cout<<v<<" ";
    cout<<endl;
}
int main()
{
    int n;
    cin>>n;//输入顶点个数
    for(int i=0;i<n-1;++i){//输入n-1条边
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    TreeToPrufer(n,g);
    return 0;
}

将一个Prufer序列转化为无根树

**方法：**设这普吕弗序列长n − 2。首先写出数1至n。第一步，找出1至n中没有在序列中出现的最小数。把标号为这数的顶点和标号为序列首项的顶点连起来，并把这数从1至n中删去，序列的首项也删去。接着每一步以1至n中剩下的数和余下序列重复以上步骤。最后当序列用完，把1至n中最后剩下的两数的顶点连起来。

算法：

使用的数据结构：假设数列A初始化为1~n的n个数。使用两个次数数组，分别记录prufer序列每个数的出现次数和数列A中每个数的出现次数。维护一个set集合：为A中有但prufe序列中没有顶点集合。

初始化次数数组和set集合
每次取出prufer序列首部u和set集合中一个最小编号顶点v。那么u,v为原图的一个无向边。然后将v从集合中删去，并判断u是否可以加入集合。
直到prufer序列为空，则取set集合内的两个顶点连成一条边。否则返回第二步。

具体实现：

时间复杂度为O(nlogn)。代码经过自己的部分测试是正确的，若有人发现bug请在评论区指出，我将尽快进行修改

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int,int> P;
const int N=1e5+10;
vector<P> tree;
int pvtimes[N],avtimes[N];
vector<int> prufer;
/* 输入:prufer序列(全局变量) 输出:prufer序列对应的tree的n-1条边 */
void PruferToTree(vector<int> &prufer)
{
    int n=prufer.size()+2;
    set<int> rem;
    tree.clear();
    mset(pvtimes,0);
    for(int v:prufer) pvtimes[v]++;

    for(int i=1;i<=n;++i) {
        avtimes[i]=1;
        if(!pvtimes[i]) rem.insert(i);
    }
    int p=0;//prufer序列首指针
    while(p<prufer.size())
    {
        int u=prufer[p],v=*rem.begin();
        tree.push_back({u,v});
        avtimes[v]=0;
        pvtimes[u]--;
        /*维护rem集合*/
        rem.erase(rem.begin());
        if(pvtimes[u]==0&&avtimes[u]>0)
            rem.insert(u);
        ++p;
    }
    auto it=rem.begin();
    int u=*it++;
    int v=(*it);
    tree.push_back({u,v});
    printf("following is tree edge of prufer:\n");
    for(P& p:tree)
        cout<<p.first<<" "<<p.second<<endl;
}
int main()
{
    int n;
    cin>>n;
    prufer.resize(n);
    for(int i=0;i<n;++i)//要求这n个顶点的范围都属于1~n+2
    {
        cin>>prufer[i];
    }
    PruferToTree(prufer);
}

例题：

洛谷P2290 树的计数:传送门

题意：输入文件第一行是一个正整数n，表示树有n个结点。第二行有n个数，第i个数表示di，即树的第i个结点的度数。其中1<=n<=150，输入数据保证满足条件的树不超过10^17个。输出满足条件的树有多少棵。

思路：根据prufer序列的性质：序列中顶点v的出现次数为v的度数-1

我们令 $a_{i} = d_{i} - 1$ ，那么问题转化为一个有n-2个数的序列，其中每个数的范围是1~n，且数 $i$ 在序列中出现了 $a_{i}$ 次，求序列的种类数。

这个答案是 $a n s = C (\frac{a_{1}}{n - 2}) * C (\frac{a_{2}}{n - 2 - a_{1}}) * . . . C (\frac{a_{n}}{n - 2 - a_{1} - a_{2} . . - a_{n - 1}}) = \frac{(n - 2)!}{Π_{i = 1}^{n} a_{i}!}$

代码:

n=int(input().strip())
du=list(map(int,input().strip().split()))
if n==1:#n=1可以存在度数为0的点
    if du[0]==0:
        print(1)
    else:
        print(0)
    exit()
sum=0
for i in du:
    if i==0:#特判度数为0,防止RE
        print(0)
        exit(0)
    sum+=i-1
if sum!=n-2:#提前判断是否不符合
    print(0)
    exit()
fac=[0 for i in range(n+1)]
fac[0]=1
for i in range(1,n+1):
    fac[i]=fac[i-1]*i
ans=fac[n-2]
for i in du:
    ans//=fac[i-1]
print(int(ans))