本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-02 11:02:16

求满足条件的树的数量：

• 大小为 $n$
• 在删除掉第 $i$ 个点及其所连接的边后剩余的连通块大小为给定数组。

保证一定有解。

Sol：

首先考虑如果给定了一棵树的根与每个点每棵子树的大小，让你求符合条件的树个数，那么直接按照子树大小分组，组合数算一下就行了（因为保证有解）。

没给定根就直接找重心，把剩下的点超过一半的连通块删掉就好了。

code

const int N=3e5+5,mod=998244353;

vector<int>v[N],ch[N];

int t[N];

\/\/init是初始化阶乘数组的，C就是C

signed main(){
	int n=read();
	int rt=0;
	for(int i=1;i<=n;i++){
		int len=read();
		bool flag=1;
		while(len--){
			int x=read();
			v[i].pb(x);
			flag&=x<=n\/2;
		}
		if(flag)
			rt=i;
	}
	init(n);
	for(int i=1;i<=n;i++){
		if(i==rt)
			continue;
		for(int j=0;j<v[i].size();j++)
			if(v[i][j]>=(n+1)\/2){
				v[i].erase(v[i].begin()+j);
				break;
			}
		int sum=1;
		sort(all(v[i]));
		int lx=0,cnt=0;
		for(int j:v[i]){
			sum+=j;
			if(j!=lx){
				ch[lx].pb(cnt);
				cnt=0;
			}
			cnt++;
			lx=j;
		}
		ch[lx].pb(cnt);
		t[sum]++;
	}
	int ans=1;
	for(int i=1;i<=n;i++){
		int sum=t[i];
		for(int j:ch[i]){
			ans*=C(sum,j);
			ans%=mod;
			sum-=j;
		}
	}
	print(ans),pc('\n');
	return 0;
}