prufer BZOJ1211: [HNOI2004]树的计数

时间：2023-03-09 20:51:48
prufer BZOJ1211: [HNOI2004]树的计数

以前做过几题。。好久过去全忘了。

看来是要记一下。。。

【prufer】

n个点的无根树（点都是标号的，distinct）对应一个 长度n-2的数列

所以 n个点的无根树有n^（n-2）种

树 转 prufer数列：  每次删除编号最小的叶子节点，将与其相连的那个点 加入 prufer数列  直到树中只剩两个点，就结束

prufer数列 转 树：  首先是有个1到n的集合G，每次将prufer数列当前的第一项 和 当前G中 不在当前prufer里有的 最小的 元素x 连边。 接着删除当前prufer中的第一项 ，并在G中删除x。。直到prufer只剩两项，两者连边 结束

对树中的i号节点 在对应的prufer数列中 出现di-1次  （di为i号节点的度）

对于i号点度数为d[i]的 无根树 树的种数有 (n - 2) ! / ( (d1 - 1)! (d2 - 1)! ……(dn - 1)! )

1211: [HNOI2004]树的计数

所以 这是道基础题 上代码吧

 #include <bits/stdc++.h>

 using namespace std;

 int n,d[],a[],b[],c[],t,k; long long x;

 void hh(int x){

     for (int i=;i<=t;++i){

         while (!(x%a[i])) x/=a[i],++b[i];

     }

 }

 int main(){

     scanf("%d",&n);

     for (int i=;i<=n;++i) {

         scanf("%d",&d[i]);

         if ((d[i]<&&n!=)||d[i]>=n) {printf("0\n"); return ;}

         x+=d[i];

     }

     if (x!=(n-)*) {printf("0\n"); return ;}

     if (n<) {printf("1\n");return ;}

     sort(d+,d++n);

     for (int i=;i<=n;++i) --d[i];

     for (int i=;i<=;++i){

         k=;

         for (int j=;j<=i-;++j)

         if (!(i%j)){k=;break;}

         if (k) a[++t]=i;

     }

     k=; while (!d[k]) ++k; while (d[k]==) ++k;

     for (int i=;i<=n;++i){

         hh(i);

         while (d[k]==i){

             for (int j=;j<=t;++j) c[j]-=b[j]; ++k;

         }

         if (n-==i) for (int j=;j<=t;++j) c[j]+=b[j];

     }

     x=;

     for (int i=;i<=t;++i)

     for (int j=;j<=c[i];++j) x*=(long long)a[i];

     printf("%lld\n",x);

     return ;

 }

Lancer

相关文章