\(Prufer\) 编码

我们希望有一个探究无根树之间的关系的工具。这里我们要讨论的工具就是Prufer编码

简介

prufer编码是一种无根树的编码方式，一个prufer编码对应唯一一颗无根树，且一颗无根树对应唯一一个prufer编码。

注意这里，我们认为两颗无根树不同，当且仅当他们的连边情况不同。同构的两颗无根树是可能不同的

---

算法

将树化为Prufer编码

按照以下方式运作

TREE << input;for i = TREE.min_leaf : TREE.size > 2    PRUFER_SEQUENCE.push_back = i.adjacent;    TREE.remove_node:i;output << PRUFER_SEQUENCE;

将Prufer编码化为树

按照以下方式运作

PRUFER_SEQURENCE << input;for i = PRUFER_SEQUENCE.elements    j = [UNIVERSE - PRUFER_SEQUENCE].min;    TREE.link: i, j;    UNIVERSE -= j;    PRUFER_SEQUENCE.pop_head;TREE.link: [UNIVERSE:1], [UNIVERSE:2]; #two elements leftoutput << TREE

证明

可以看到对于一个树的输入，可以得到唯一的编码输出，对于唯一的编码输入也可以得到唯一的树的输出。关键是证明对于一个编码输出，只会有唯一的树的输入。

递归的考虑当前构造出的子图，设\(n\)节点无根树\(A,B\)拥有相同的编码设为\(p\)，设\(A',B'\) 为\(A,B\)当前构造出的子图。当前考虑到了第\(i\)位，那么｛\(p_i\)～\(p_n\)｝＝｛\(A'\)和\(B'\)的非叶节点｝，就是说｛\(A'\)的非叶节点｝＝｛\(B'\)的非叶节点｝。那么最小叶节点也是一定的，与其的连边也是确定的。则确定了\(n-2\)条边。那么我们也能够知道图中最后剩下的两个节点，确定他们之间的边，则确定了全部的\(n-1\)条边。

推广

1. 编码中节点出现次数就是原树该点的度数-1。
2. \(Cayley\)公式: 对于n个节点的完全图\(K_n\)，有\(n^{n-2}\)颗生成树

请读者自行证明

例题

给你一个树每个点的度数限制，求方案数。

由推广2，利用prufer编码，转化为一个直观的排列组合问题：\(n-2\)个prufer编码的位置上分配不同个数的点的方案数。其中m个节点不限制度数。下面给出式子：

\[ Answer = [\prod^{n-m}_{i=1} \binom{d_i}{n-2-\sum^{i-1}_{j=1}d_j}]*[m^{n-2-\sum^{n}_{i=1}d_i}] \]

\[ = [\prod^{n-m}_{i=1} \frac{(n-2-\sum^{i-1}_{j=1}d_j)!}{d_i!(n-2-\sum^{i}_{j=1}d_j)!}]*[m^{n-2-\sum^{n}_{i=1}d_i}] \]

\[ = \frac{(n-2)!}{[\prod_{i=1}^{n-m}d_i!]*(n-2-\sum_{i=1}^{n-m}d_i)!}*m^{n-2-\sum^{n-m}_{i=1}d_i} \]

需要高精，即除法以约去质因数为替。

代码如下：

#include 
    
     #include 
     
      #include 
      
       const int N = 1010, W = 1000000;int ans[N],f[N][N],p[N],prime[N],d[N],tot,n,m,sum,cnt,i,j,x,head;bool check[N];void mul(int k){    for(int i = 0;i <= head;i ++)ans[i] *= k;    for(int i = 0;;++i>head?head++:i)    {        if(i==head && ans[i]
       
        =W){ans[i+1]+=ans[i]/W, ans[i]%=W;}    }}int main(){    scanf("%d",&n);    if(n==1) {        scanf("%d",&x);        if(x==0)printf("1\n");        else printf("0\n");        return 0;    }    for(int i = 0;i < n;i ++) {        scanf("%d",&x);         if(x==0){printf("0\n");return 0;}        if(x==-1)m++;else {d[cnt++]=x-1;sum+=x-1;}    }    if(sum>n-2){printf("0\n");return 0;}    ans[0] = 1;    for(int i = 2;i <= n;i ++) {        if(!check[i])prime[tot++] = i;        for(int j = 0;j < tot;j++)        {            if(prime[j]*i>n)break;            check[prime[j]*i] = true;            if(i%prime[j]==0)break;        }    }    for(int i = 2;i <= n;i ++)        for(int j = 0;j < tot;j++)        {            int x = i; while(x%prime[j]==0){x/=prime[j];f[i][j]++;}            f[i][j] += f[i-1][j];        }    int q = sqrt(n);    for(int i = 0;i < tot;i ++)p[i] = f[n-2][i];    d[cnt++] = n-2-sum;    for(int i = 0;i < cnt;i ++)        for(int j = 0;j < tot;j ++)            p[j] -= f[d[i]][j];    for(int i = 0;i < tot;i ++)        for(int j = 0;j < p[i];j++)            mul(prime[i]);    for(int i = 0;i < n-2-sum;i ++) mul(m);    for(int i = head;~i;i --)        if(i==head)printf("%d",ans[i]);        else printf("%06d",ans[i]);    printf("\n");    return 0;}
       
      
     
    

天哪，丑的我自己都看不下去了。。。

参考

---

待续未完

我现在只写了这一道prufer的题啊，下次遇到继续更新！