题解：P11298 [NOISG2018 Prelim] Island

· · 题解

水题。

假设固定节点 1 的位置，这样答案最后就不用除以 n 了。

那么我们从 1 开始 dfs，令 f_u 为以 u 为根的子树的排列方案数，s 为 u 儿子个数，那么有 f_u=\prod f_v\times s!，因为儿子的排列可以随便换，每种换出来的都不一样。

那么答案就被转化为所有 2 到 n+m 的点的 e_u-1 乘积再乘上 e_1，因为除了 1 之外其他点的儿子数量就等于边数减一，其中 e_x 表示 x 的度数。

对于每一个点的贡献在数组上面记录，然后做一个后缀就可以求出对于每一个数在答案中有几个。

for(int i=1;i<n+m;i++){
    int u,v;
    cin>>u>>v;
    ecnt[u]++,ecnt[v]++;
}
p[ecnt[1]]++;
for(int i=2;i<=n+m;i++) p[ecnt[i]-1]++;
int s=0;
for(int i=n+m;i>=2;i--){
    s+=p[i];
    p[i]=s;
    if(p[i]) cout<<i<<" "<<p[i]<<endl;
}