「JSOI2019」神经网络
考虑一个合法的哈密顿路可以表示为什么样子：
按照不同树的编号，分割为一段段，相邻两段属于不同树
同时，如果最后一段和第一段同编号，将最后一段移动到第一段前面
由此，一个哈密顿路可以由唯一表示：
1号点在第一个段中，此后每一段和上一个属于不同树，且最后一段不属于1树
由此，问题分解为两部分：
Part1 求解树路径分段
考虑树形(dp)求解，每个点记录(dp_{i,j,0/1})表示当前(i)子树内已经产生(j)条路径，(i)自己是否可以向父亲连边
容易用类似树形背包的方式合并，每次决策儿子是否连接到自己上面
注意：一个长度(>1)的段，需要考虑正反方向的排放
复杂度为(O(sum k_i^2))
[
]
Part2 合并每棵树的段
相邻两段不同色，考虑容斥求解
枚举这棵树中的(i)个段自己生成了(j)个不合法的相邻，(i)个段合并生成(i-j)个段，且乘上容斥系数((-1)^j)
(i)个并掉(j)个，方案数计算如下：
先把(i)个排好，乘上(i!)，然后选择(j)个间隔合并掉(inom{i-1}{j})，然后对于剩下的(i-j)个元素无序，需要除掉((i-j)!)
背包合并容斥之后的结果，对于当前的(i)个元素，任意排列即可
然而上面是理想情况，还需要考虑(1)号元素不能被排列，要强制最后一个段不是1树的段
这一部分，在树1的容斥以及最终背包合并时特殊处理即可，即少排列一个元素，且最后合并时先选一个放在最后面
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
template <class T=int> T rd(){
T s=0; int f=0;
while(!isdigit(IO=getchar())) f|=IO=='-';
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=5e3+10,P=998244353;
int n,m;
int I[N],J[N],C[N][N];
ll qpow(ll x,ll k=P-2) {
ll res=1;
for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
return res;
}
struct Edge{
int to,nxt;
} e[N<<1];
int head[N],ecnt;
void AddEdge(int u,int v){
e[++ecnt]=(Edge){v,head[u]};
head[u]=ecnt;
}
int dp[N][N][2]; // 0,1 是否向上连
int G[N][3],H[N][3],sz[N];
void dfs(int u,int f){
sz[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f) continue;
dfs(v,u);
}
G[0][0]=1,G[0][1]=G[0][2]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f) continue;
rep(i,0,sz[u]+sz[v]) rep(j,0,2) H[i][j]=G[i][j],G[i][j]=0;
rep(i,0,sz[u]) rep(a,0,2) if(H[i][a]) rep(j,0,sz[v]) rep(b,0,min(1,2-a)) G[i+j][a+b]=(G[i+j][a+b]+1ll*H[i][a]*dp[v][j][b])%P;
sz[u]+=sz[v];
}
rep(i,0,sz[u]+1) dp[u][i][0]=dp[u][i][1]=0;
rep(i,0,sz[u]) {
dp[u][i+1][0]=(0ll+dp[u][i+1][0]+G[i][0]+2*G[i][1]+2*G[i][2])%P; // 长度>1的段可以翻转
dp[u][i][1]=(0ll+dp[u][i][1]+G[i][0]+G[i][1])%P; // 如果连了两个儿子，就无法向上连了
}
sz[u]++;
}
int F[N],T[N];
void Get(){
n=rd();
rep(i,1,n) head[i]=0;
ecnt=0;
rep(i,2,n) {
int u=rd(),v=rd();
AddEdge(u,v),AddEdge(v,u);
}
dfs(1,0);
rep(i,1,n) {
F[i]=dp[1][i][0],T[i]=0;
ll t=1ll*F[i]*J[i]%P;
rep(j,1,i) {
T[j]=(T[j]+((i-j)&1?P-1:1)*t%P*C[i-1][i-j]%P*I[j])%P;
}
}
}
int S[N],c;
int main(){
rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
I[N-1]=qpow(J[N-1]);
drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
rep(i,0,N-1) rep(j,C[i][0]=1,i) C[i][j]=C[i-1][j]+C[i-1][j-1],Mod1(C[i][j]);
m=rd();
if(m==1) return n=rd(),printf("%d
",n<=2),0;
S[0]=1;
rep(t,1,m-1) {
Get();
drep(i,n+c,0) {
S[i]=0;
rep(j,1,min(i,n)) S[i]=(S[i]+1ll*S[i-j]*T[j])%P;
}
c+=n;
}
Get();
rep(i,1,n) {
F[i]=dp[1][i][0],T[i]=0;
ll t=1ll*F[i]*J[i-1]%P;
// 特殊处理，不允许排列第一段
rep(j,1,i) T[j]=(T[j]+((i-j)&1?P-1:1)*t%P*C[i-1][i-j]%P*I[j-1])%P;
}
int ans=0;
// 不允许改变第一段的位置
// 且强制最后一段不能属于第一棵树
rep(i,1,c) if(S[i]) rep(j,1,n) if(T[j]) {
// 强制前面的最后一个在最后
int t=1ll*J[i]*J[j-1]%P*C[i-1+j-1][j-1]%P;
ans=(ans+1ll*t*S[i]%P*T[j])%P;
}
printf("%d
",ans);
}