题目描述
题目背景
火星探险队发现,火星人的思维方式与人类非常不同,是因为他们拥有与人类很不一样的神经网络结构。为了更好地理解火星人的行为模式,JYY 对小镇上火星人的大脑进行了扫描,得到了一些重要数据。
题目描述
火星人在出生后,神经网络可以看作是一个由若干无向树 {T1(V1,E1),T2(V2,E2),…Tm(Vm,Em)} 构成的森林。随着火星人年龄的增长,神经连接的数量也不断增长。初始时,神经网络中生长的连接 E∗=∅。神经网络根据如下规则生长:
- 如果节点 u∈Vi,v∈Vj 分别属于不同的无向树 Ti 和 Tj (i=j),则 E∗ 中应当包含边 (u,v)。
最终,在不再有神经网络连接可能生长后,神经网络之间的节点连接可以看成是一个无向图 G(V,E),其中
V=V1∪V2∪…∪Vm,E=E1∪E2∪…∪Em∪E∗
火星人的决策是通过在 G(V,E) 中建立环路完成的。针对不同的外界输入,火星人会建立不同的神经连接环路,从而做出不同的响应。为了了解火星人行为模式的复杂性,JYY 决定计算 G 中哈密顿回路的数量。
G(V,E) 的哈密顿回路是一条简单回路,从第一棵树的第一个节点出发,恰好经过 V 中的其他节点一次且仅一次,并且回到第一棵树的第一个节点。
输入格式
第一行读入 m,表示火星人神经网络初始时无向树的数量。
接下来输入有 m 部分,第 i 部分描述了树 Ti。
对于 Ti,输入的第一行是树 Ti(Vi,Ei) 中节点的数量 ki。假设 Vi={v1,v2,…,vki}。
接下来 ki−1 行,每行两个整数 x,y,表示该树节点 vx,vy (1≤x,y≤ki) 之间有一条树边,即 (vx,vy)∈Ei。
输出格式
因为哈密顿回路的数量可能很多,你只需要输出一个非负整数,表示答案对 998244353 取模后的值。
样例
2
3
1 2
1 3
2
1 2
12
在这个样例中,G 中一共有 5 个点,只有第一棵树的 2,3 节点之间没有边,其他任意两个点之间都存在边。这样的图哈密顿回路个数为 12。
见附加文件 neural2.in/ans
。
数据范围与提示
测试点 |
∑i=1mki |
m |
ki |
树形态限制 |
1 |
≤10 |
≤3 |
无限制 |
无限制 |
2 |
≤15 |
≤4 |
3 |
≤600 |
≤300 |
≤2 |
4∼6 |
≤900 |
≤3 |
7∼10 |
2.5×103 |
50 |
50 |
11∼14 |
≤5×103 |
≤300 |
无限制 |
每棵树都是链 |
15∼20 |
无限制 |