【2018/10/30测试T1】排列树

【题目】

传送门

【分析】

记 $size_i$sizei​ 表示 $i$i 号点的子树大小，$f_i$fi​ 表示以 $i$i 为根的子树分配 $size_i$sizei​ 个标号的方案数。

实际上，不同子树里的标号是互不影响的，因为它们的标号只跟根有关系

而求 $f_i$fi​ 的话，可以用组合数来求到，举个例子，假如子树 $x$x 的大小为 $size_x$sizex​，而 $x$x 有个子树大小为 $size_i$sizei​，那就相当于在 $size_x$sizex​ 中选 $size_i$sizei​ 个分配给 $i$i，就是组合数啦，然后就根据乘法原理，把所有方案乘起来就是答案了

时间复杂度 O$(n)$(n)。

$Ps$Ps：组合数可以通过预处理出阶乘和阶乘的逆元得到

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000005
#define Mod 998244353
using namespace std;
int n,t,ans;
int inv[N],fac[N],sze[N];
int first[N],v[N],nxt[N];
void add(int x,int y)
{
	t++;
	nxt[t]=first[x];
	first[x]=t;
	v[t]=y;
}
int Power(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)
		  ans=(1ll*ans*a)%Mod;
		a=(1ll*a*a)%Mod;
		b>>=1;
	}
	return ans;
}
int C(int m,int n)
{
	return 1ll*fac[n]*inv[m]%Mod*inv[n-m]%Mod;
}
void init()
{
	int i;
	fac[0]=fac[1]=1;
	for(i=2;i<=n+1;++i)  fac[i]=1ll*fac[i-1]*i%Mod;
	inv[n+1]=Power(fac[n+1],Mod-2);
	for(i=n;i>=0;--i)  inv[i]=1ll*(i+1)*inv[i+1]%Mod;
}
void find(int x,int father)
{
	int i,j;
	sze[x]=1;
	for(i=first[x];i;i=nxt[i])
	{
		j=v[i];
		if(j!=father)
		{
			find(j,x);
			sze[x]+=sze[j];
		}
	}
	int num=sze[x]-1;
	for(i=first[x];i;i=nxt[i])
	{
		j=v[i];
		if(j!=father)
		{
			ans=1ll*ans*C(sze[j],num)%Mod;
			num-=sze[j];
		}
	}
}
int main()
{
//	freopen("tree.in","r",stdin);
//	freopen("tree.out","w",stdout);
	int x,y,i;
	scanf("%d",&n);
	for(i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	init();
	ans=1,find(1,0);
	printf("%d",ans);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}