#3102. 「JSOI2019」神经网络

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目背景

火星探险队发现,火星人的思维方式与人类非常不同,是因为他们拥有与人类很不一样的神经网络结构。为了更好地理解火星人的行为模式,JYY 对小镇上火星人的大脑进行了扫描,得到了一些重要数据。

题目描述

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

  • 如果节点 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 中的其他节点一次且仅一次,并且回到第一棵树的第一个节点。

输入格式

第一行读入 m ,表示火星人神经网络初始时无向树的数量。
接下来输入有 m 部分,第 i 部分描述了树 T_i
对于 T_i ,输入的第一行是树 T_i(V_i, E_i) 中节点的数量 k_i 。假设 V_i = \{v_1, v_2,\ldots ,v_{k_i}\}
接下来 k_{i} - 1 行,每行两个整数 x, y ,表示该树节点 v_x, v_y\ (1 \le x, y \le k_i) 之间有一条树边,即 (v_x, v_y) \in E_i

输出格式

因为哈密顿回路的数量可能很多,你只需要输出一个非负整数,表示答案对 998244353 取模后的值。

样例

样例输入 1

2
3
1 2
1 3
2
1 2

样例输出 1

12

样例说明 1

在这个样例中, G 中一共有 5 个点,只有第一棵树的 2, 3 节点之间没有边,其他任意两个点之间都存在边。这样的图哈密顿回路个数为 12

样例 2

见附加文件 neural2.in/ans

数据范围与提示

测试点 \sum_{i=1}^m k_i m k_i 树形态限制
1 \le 10 \le 3 无限制 无限制
2 \le 15 \le 4
3 \le 600 \le 300 \le 2
4\sim 6 \le 900 \le 3
7\sim 10 2.5\times 10^3 50 50
11\sim 14 \le 5\times 10^3 \le 300 无限制 每棵树都是链
15\sim 20 无限制