0 前置知识点

• 排列组合
• 高精度 / 分解质因数

1 Prufer 序列

对于一个带编号的无根树，其 Prufer 序列按以下过程处理

1. 选取所有节点中度数最小编号最小的一个节点
2. 输出其相邻的编号
3. 回到 1 ，直到只剩两个节点为止

每个 Prufer 序列，都对应唯一的一个带编号的无根树

按照以下步骤即可从 Prufey 序列变成一棵树

1. 选取在数列中没有出现过的数字且未标记最小的一个，将其标记
2. 其为当前序列中第一个节点的儿子
3. 将第一位移出 Prufey 序列，回到步骤 1

因为算法可以一直进行下去，所以任意 Prufey 编码对应一个带编码的无根树

所以无向图的生成树个数为 $n^{n – 2}$ ， 这就是 Cayley 公式啦！

2 题目

题目链接: https://www.luogu.org/problemnew/show/P2290

根据 Prufer 序列的性质可得

度数为 $x$ 的点在 Prufer 序列中会出现 $x – 1$ 次

则给定度数的无根树总共会有
$$
\frac{ (n – 2)! }{\prod_{i = 1}^n (d_i – 1)!}
$$
众情况

其中

• $d_i$ 为 $i$ 点的度数

可以这么理解

$ (n – 2) !$ 是全排列

$\prod_{i = 1}^n (d_i – 1)!$ 是去除重复计算的情况

然后很明显，这个代码会爆 long long ,所以要么高精度，要么分解质因树

代码

#include <cstdio>
#include <cstring>

const int BASE = 10;

struct Bigint {
    int num[11000], cnt;
    Bigint() {
        cnt = 0;
        memset(num, 0, sizeof(num));
    }
    int& operator[] (int now) { return num[now]; }
    void operator*= (int now) {
        for(int i = 1; i <= cnt; i ++)
            num[i] *= now; 
        for(int i = 1; i <= cnt; i ++){
            if( num[i] >= BASE ) {
                num[i + 1] += num[i] / BASE;
                num[i] %= BASE;
            }
        }
        while(num[cnt + 1] != 0){
            cnt ++;
            if( num[cnt] >= BASE ) {
                num[cnt + 1] += num[cnt] / BASE;
                num[cnt] %= BASE;
            }
        }
    }
    void operator/= (int now){
        for(int i = cnt; i; i --){
            num[i - 1] += (num[i] % now * 10);
            num[i] /= now;
        }
        while( !num[ cnt ] )
            cnt --;
    }
    void to_bigint(int now) {
        while(now) {
            num[ ++ cnt ] = now % BASE;
            now /= BASE;
        }
    }
    void print(char end = 0) {
        for(int i = cnt; i; i --)
            printf("%d", num[i]);
        end && putchar(end);
    }
};

int main() {
#ifdef woshiluo
    freopen("luogu.2290.in", "r", stdin);
    freopen("luogu.2290.out", "w", stdout);
#endif
    int n, d[1100], sum = 0;
    scanf("%d", &n);
    // 特判 1 的情况
    if(n == 1){
        scanf("%d", &d[1]);
        if(!d[1])
            printf("1");
        else 
            printf("0");
        return 0;
    }
    for(int i = 1; i <= n; i++){
        scanf("%d", &d[i]);
        if(d[i] == 0){
            printf("0");
            return 0;
        }
        sum += d[i] - 1;
    }
    Bigint ans; ans.to_bigint(1);
    for(int i = 1; i <= n - 2; i++)
        ans *= i;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j < d[i]; j++)
            ans /= j;
    if(sum == n - 2) 
        ans.print();
    else {
        printf("0");
        return 0;
    }
}