自动搬运

查看原文

来自洛谷，原作者为

	xiaoliebao1115 real life

搬运于2025-08-24 23:06:12，当前版本为作者最后更新于2024-11-22 16:33:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

水题。

假设固定节点 $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;
}