题解 P2290 【[HNOI2004]树的计数】

Gary818 · 2019-07-21 19:02:04 · 题解

虽然这题A了很久了，但是今天才算真正搞懂
说实话，我开始并没有看懂题目意思QAQ
然而就是一个裸的prufer序列
还是从样例入手

4  
2 1 2 1

画个图解释一下

题目中给出的样例只有这两种情况，所以输出答案为2
我们更关心答案怎么来的，下面来讲一下prufer序列

prufer序列

prufer序列是一种对有标号无根树的编码，长度为节点数-2
具体地，存在无根树转为prufer序列以及prufer序列转为无根树两种操作，换言之，上述两者是互射的（可以互相转化）
无根树转prefer
1.找到编号最小且度数为1的点
2.删除该节点，并且在序列中添加与该节点连接的节点
3.重复1、2操作，直至下树上只剩下两个点（此时在进行操作没有意义，所以停止，也就是为什么序列长度为节点数-2）
prefer转无根树
1.设prufer序列为集合M，另一个集合 G { 1,2,3…n }
2.每次提取M中最靠前的元素u与G中不存在与M且最靠前的元素v，将u与v连边，分别在两个集合中删除u、v。
3.最后将G中剩下的两个元素连边

举个栗子
看上面的第一个图

图转prufer序列
先找到2，删除2和2->1连边，将1入列，删除1和1->3连边，3入列，序列就是“1，3”

prufer序列转图
取出M中的1和G中的2连边，分别删除两个集合中的元素取出M中的3和G中的1连边，然后……同上……
此时，M空了，G中只剩下了3，4，连接3，4就行了
图就建好了
自己手模一遍，不难

对于这道题 (n-2)!/((d1-1)!×(d2-1)!×…×(dn-1)!)

特判几个地方就哦可，尤其是当转换prufer序列的时候，如果入列次数！=n-2，就一定有问题，输出0
还有，如果有的节点度数为0，那图就不联通，那就输出0
就这几个细节，然后组合数打个表就AC了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=155;
int c[maxn][maxn];
int ans,d[maxn];
int sum;
int n;

inline void pre(){
    for(int i=0;i<=n;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
}

int main(){
    cin>>n;
    if(n==1){
        cin>>d[1];
        if(d[1]==0) cout<<1<<endl;
        else cout<<0<<endl;
        return 0;
    }
    pre();
    for(int i=1;i<=n;i++){
        cin>>d[i];
        if(!d[i]) return cout<<0<<endl,0;
        d[i]--;
        sum+=d[i];
    }
    if(sum!=n-2) return cout<<0<<endl,0;
    sum=0,ans=1;
    for(int i=1;i<=n;i++)
        ans*=c[n-2-sum][d[i]],sum+=d[i];
    cout<<ans<<endl;
    return 0;
}

AC
完结撒花～～～