题解：CF156D Clues /【模板】广义 Cayley 定理

· · 题解

很久以前就在 OI wiki 上看过，但一直都没看证明，来补课了。

我不知道但是 deepseek 管这个叫做广义 Cayley 定理来着。

题意：

一个 n 个点 m 条边的带标号无向图有 k 个连通块。我们希望添加 k-1 条边使得整个图连通。求方案数。

结论：

设第 i 个连通块大小为 s_i，那么答案为 n^{k-2}\prod_{i=1}^k s_i。

证明：

参考了这篇题解和这篇题解以及 OI wiki 的对应部分。

首先考虑把连通块缩成点，然后考虑怎么计算在这个情况下能连出的有标号无根树的数量。

显然 Cayley 定理我们有 k^{k-2}，证明的话就是树的 prufer 序列的长度一定是 k-2，然后每个位置上可以任意填块的编号。

考虑 prufer 序列是怎么和树对应起来的。

每次我们删除掉一个度数为 1 的编号最小的节点，然后把与其相邻的节点给写上去。

考虑我们不写块编号了，直接写这个边指向的实际点编号，所以一个位置可以填 n 个数，总序列数量为 n^{k-2}。

考虑一个序列可以构造出几个真实的树。

原始 prufer 序列构造树的时候，我们依次删除度数为 1 且编号最小的未构造节点，将其与 prufer 序列上对应块相连。现在我们指定了一端的连接点，那么对于删除的这个连通块就会产生 s_i 的贡献。

最后我们会剩下两个块没删，显然中间这个边的情况数恰好是两个块大小的乘积，于是每个连通块的大小都要乘上去作贡献。

因此答案恰好就是：

\boxed{n^{\,k-2} \prod_{i=1}^k s_i} 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int fa[100005];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int n,m,mod;
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int siz[100005];
signed main(){
    cin>>n>>m>>mod;
    if(mod==1){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++)
    fa[i]=i;
    while(m--){
        int u,v;
        cin>>u>>v;
        fa[find(u)]=find(v);
    }
    for(int i=1;i<=n;i++)
    siz[find(i)]++;
    int ans=1,k=0;
    for(int i=1;i<=n;i++)
    if(find(i)==i)ans=ans*siz[i]%mod,k++;
    if(k==1){
        cout<<1;
        return 0;
    }
    ans=ans*qpow(n,k-2)%mod;
    cout<<ans;
    return 0;
}
// 芙莉莲。
// 动手。

// 说的也是。
// 辛美尔的话肯定会这么说的。