不会 Prüfer 序列

· · 题解

Prüfer 序列是大佬才能使用的“经典结论”，像我这样的渣滓根本不配。

n = m - 1

树计数，我们先随便钦定一个根，比如最后一个节点。

在树的情况下，根据定义，可知 a_i 即为节点 i 的度数。但是树的非根节点的度数有一个更好入手方式：儿子个数 +1。

我们考虑一种更适合普通人类的树计数方式：插入。

我们先把所有叶子（a_i=1 的节点）排成一行，它们目前是“树顶”。

每次插入一个节点，把这个节点的度数分成 1+1+x 三份考虑：一个留给父亲，一个可以任选之前的某个节点做儿子，剩下的选一些“树顶”做儿子。最后除以 (a_i-1)! 给所有儿子消除顺序。

最后一个节点不做插入，因为它是我们钦定的根，如果数据合法必然有最后“树顶”个数等于 a_n。

其实代码更好懂……


void solve() {
    // 已经提前将 a 数组排序，保证 a_i=1 在最前面
    int ans = 1；
    int deg = 0; // 树顶个数
    for (int i = 1; i < n; ++ i) {
        if (a[i] == 1) {
            ++ deg;
            continue;
        }
        ans = (lnt) A(deg - 1, a[i] - 2) // 有序选择
            % M * (i - 1)
            % M * vca[a[i] - 1]
            % M * ans % M
        ;
        deg -= a[i] - 2; // 树顶会减少 a_i-2 个。
    }
    cout << ans << '\n';
}

n = m

基环树。

我们尝试从树的算法上推广。

容易发现，将环上的边全部断掉，并将原先在环上的点作为余下森林的每棵树的根，对于任意节点（包括原先在环上的点）均有 a_i 等于其儿子个数加一。

那么我们直接跑上面的算法，这次最后一个节点也一样加进去。然后只需要剩余的“树顶”连接成环即可。

基本一样的代码。

void solve() {
    int ans = 1, deg = 0;
    for (int i = 1; i <= n; ++ i) {
        // 一模一样
        // ...
    }
    cout << (lnt) ans * ica[deg - 1] % M * vca[2] % M << '\n';
}

n = m+1，a_i=1

那么整个图构成一个点双。

只可能是两个节点夹三条链。

那么：

cout << (lnt) n * (n - 1) / 2 % M * vca[3] % M * (
    (lnt) ica[n] * vca[2] % M +  // 从 3 乘到 n
    (lnt) (M - ica[n - 2]) * 3   // 选一条链，排列
) % M << '\n';

n=m+1 且两环有公共边。

人话：只有一个大点双。

同基环树的操作方式。如果将大点双内的所有边去掉，对于任意节点均有 a_i 等于其儿子个数加一。

那么就只需要把基环树最后一步的“连接成环”改为“连接成大点双”即可。

再一看，这个最后一步不就是上面 a_i=1 的情况吗……

void solve() {
    int ans = 1, deg = 0;
    for (int i = 1; i <= n; ++ i) {
        // 一模一样
        // ...
    }
    return (lnt) deg * (deg - 1) / 2 % M * vca[3] % M * (
        (lnt) ica[deg] * vca[2] % M +
        (lnt) (M - ica[deg - 2]) * 3
    ) % M * ans % M;
}

n=m+1 且两环没公共边。

我们考虑直接跑基环树，那么现在还要造一个环上去。

此时这个基环上的点数为实际情况两环点数之和 -2。

那么我们直接随便选一条非基环上的边拆了，不就把度数补上了嘛。非基环上的边，即为所有非树顶节点的连向父亲的边，所以有 n-deg 个。

然后我们再从基环上取一段后缀分给新环。图要合法，所以环至少要 3 条边，所以剩下的边数的合法取值区间为 [3,deg)， 方案数为 deg - 3。

两个环要分别消除顺逆。同时两环地位等同，还要消除对面分裂出这边的情况。一共除以 8。

void solve() {
    int ans = 1, deg = 0;
    for (int i = 1; i <= n; ++ i) {
        // 一模一样
        // ...
    }
    return (lnt) (deg - 3) * (n - deg)
        % M * ica[deg - 1] // 这行和下面一个2，就是基环树
        % M * vca[2]
        % M * vca[2]
        % M * vca[2]
        % M * ans
        % M
    ;
}

后记

模拟赛拿到 80 分就没做了……

其实最后一个部分是观察小数据凑出来的，最后整理发现了很好的组合意义。