Description

火星人在出生后，神经网络可以看作是一个由若干无向树 /(/{T_1(V_1, E_1), T_2(V_2, E_2),/ldots T_m(V_m, E_m)/}/) 构成的森林。随着火星人年龄的增长，神经连接的数量也不断增长。初始时，神经网络中生长的连接 /(E^/ast = /varnothing/)。神经网络根据如下规则生长：

• 如果节点 /(u /in V_i, v /in V_j/) 分别属于不同的无向树 /(T_i/) 和 /(T_j/)（/(i /neq j/)），则 /(E^/ast/) 中应当包含边 /((u, v)/)。

最终，在不再有神经网络连接可能生长后，神经网络之间的节点连接可以看成是一个无向图 /(G(V,E)/)，其中

/[V=V_1/cup V_2/cup /ldots /cup V_m,E=E_1/cup E_2/cup /ldots /cup E_m/cup E^/ast
/]

火星人的决策是通过在 /(G(V, E)/) 中建立环路完成的。针对不同的外界输入，火星人会建立不同的神经连接环路，从而做出不同的响应。为了了解火星人行为模式的复杂性，JYY 决定计算 /(G/) 中哈密顿回路的数量。

/(G(V, E)/) 的哈密顿回路是一条简单回路，从第一棵树的第一个节点出发，恰好经过 /(V/) 中的其他节点一次且仅一次，并且回到第一棵树的第一个节点。

Solution

题目限制的哈密顿回路等价于将给出的树划分成若干条链，按照任意顺序将不属于同一棵树的链连接成一张大环的方案数

这里唯一的限制就是不能让两个属于同一棵树的链在路径中相邻，这部分后面将使用容斥进行计算

首先使用树上背包计算将每棵树划分成若干条链的方案数，这里长度超过 /(1/) 的链要附加 /(2/) 的系数，因为可以双向通过

设 /(f_{i,j,0/1/2}/) 表示 /(i/) 号点的子树中划分成了 /(j/) 条链，且根在链上的度数为 /(0/1/2/) ，转移分为是否将根和当前归并的子树根所在的链连接起来，式子可以写作：

/[/begin{aligned}f_{x,i+j,k}&/leftarrow f_{x,i,k}(f_{t,j,0}+2f_{t,j,1}+f_{t,j,2})//f_{x,i+j-1,1}&/leftarrow f_{x,i,0}(f_{t,j,0}+f_{t,j,1})//f_{x,i+j-1,2}&/leftarrow f_{x,i,1}(f_{t,j,0}+f_{t,j,1})/end{aligned}
/]

这里是在每条链确定和再浅的点没有联系之后将 /(2/) 的系数附加的

尝试使用 /(/rm EGF/) 计算形成若干条链的方案数，对相邻且在同一棵树上的链进行容斥：

/[/sum_{i=1}^nf_ii!/sum_{j=0}^{i-1} (-1)^j/binom{i-1}j/frac{x^{i-j}}{(i-j)!}
/]

第二个求和符号中枚举有几个空隙填了相同的元素，也就是最后保留了 /(i-j/) 条链，该容斥系数的正确性可以通过简单组合恒等式得到

此时遗留问题就是第一条和最后一条链可能在同一棵树上，特殊化第一棵树的第一个点所在的链，重新给它编 /(/rm EGF/) ：

由于钦定起点，那么第一棵树参与任意排列的链数减少 /(1/)，写作

/[/sum_{i=1}^nf_i(i-1)!/sum_{j=1}^{i} (-1)^{i-j}/binom{i-1}{i-j}/frac{x^{j-1}}{(j-1)!}
/]

强制首尾的链相同的情况也是类似的，有两个链不计入最后 /(/rm EGF/) 的排列即可：

/[/sum_{i=1}^nf_i(i-1)!/sum_{j=2}^{i} (-1)^{i-j}/binom{i-1}{i-j}/frac{x^{j-2}}{(j-2)!}
/]

使用 /(/Theta(n^2)/) 卷积！

Code

const int N=5010;
vector<int> G[N];
inline vector<int> Mul(vector<int> &a,vector<int> &b){
	int n=a.size(),m=b.size();
	vector<int> res(n+m-1);
	for(int i=0;i<n;++i) for(int j=0;j<m;++j) res[i+j]+=a[i]*b[j]%mod;
	for(int i=0;i<n+m-1;++i) res[i]%=mod;
	return res;
}
int C[N][N],fac[N],ifac[N],tmp[N][3];
signed main(){
	C[0][0]=ifac[0]=fac[0]=1;
	for(int i=1;i<=5000;++i){
		C[i][0]=1;
		fac[i]=mul(fac[i-1],i);
		ifac[i]=ksm(fac[i],mod-2);
		for(int j=1;j<=i;++j) C[i][j]=add(C[i-1][j],C[i-1][j-1]);
	}
	int T; scanf("%lld",&T);
	vector<int> ans={1};
	bool mark=0;
	while(T--){
		int n;
		scanf("%lld",&n);
		for(int i=1;i<n;++i){
			int u,v;
			scanf("%lld%lld",&u,&v);
			G[u].emplace_back(v);
			G[v].emplace_back(u);
		}
		vector<vector<int> >dp[3];
		rep(i,0,2) dp[i].resize(n+1);
		vector<int> siz(n+1);
		function<void(int,int)>dfs=[&](int x,int fat){
			siz[x]=1;
			int sum=1;
			for(auto t:G[x]) if(t!=fat) dfs(t,x),sum+=siz[t];
			dp[0][x].resize(sum+1);
			dp[1][x].resize(sum+1);
			dp[2][x].resize(sum+1);
			dp[0][x][1]=1;
			for(auto t:G[x]) if(t!=fat){
				for(int i=1;i<=siz[x];++i){
					for(int j=1;j<=siz[t];++j){
						rep(k,0,2) tmp[i+j][k]+=dp[k][x][i]*(dp[0][t][j]+2*(dp[1][t][j]+dp[2][t][j]))%mod;
						tmp[i+j-1][1]+=dp[0][x][i]*(dp[0][t][j]+dp[1][t][j])%mod;
						tmp[i+j-1][2]+=dp[1][x][i]*(dp[0][t][j]+dp[1][t][j])%mod;
					}
				}
				siz[x]+=siz[t];
				for(int i=1;i<=siz[x];++i){
					rep(j,0,2) dp[j][x][i]=tmp[i][j]%mod,tmp[i][j]=0;
				}
			}
			G[x].clear();
			return ;
		};
		dfs(1,0);
		vector<int>f(n+1),poly(n+1);
		for(int i=1;i<=n;++i) f[i]=(dp[0][1][i]+2*(dp[1][1][i]+dp[2][1][i]))%mod;
		if(!mark){
			for(int i=1;i<=n;++i){
				int coef=mul(fac[i-1],f[i]);
				for(int j=1;j<=i;++j){
					if((i-j)&1) poly[j-1]-=coef*C[i-1][j-1]%mod;
					else poly[j-1]+=C[i-1][j-1]*coef%mod;
				}
				for(int j=2;j<=i;++j){
					if((i-j)&1) poly[j-2]+=C[i-1][j-1]*coef%mod;
					else poly[j-2]-=C[i-1][j-1]*coef%mod;
				}
			}
			mark=1;
		}else{
			for(int i=1;i<=n;++i){
				int coef=mul(fac[i],f[i]);
				for(int j=1;j<=i;++j){
					if((i-j)&1) poly[j]-=C[i-1][j-1]*coef%mod;
					else poly[j]+=C[i-1][j-1]*coef%mod;
				}
			}
		}
		for(int i=0;i<=n;++i){
			poly[i]=(poly[i]%mod+mod)%mod;
			ckmul(poly[i],ifac[i]);
		}
		ans=Mul(ans,poly);
	}
	int sum=0;
	for(int i=1;i<ans.size();++i) sum+=ans[i]*fac[i]%mod;
	printf("%lld/n",sum%mod);
	return 0;
}