#2409. 神经网络

    ID: 2409 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest890来源:qoj.ac数据:公开样例图论树上算法

神经网络

神经网络

题目描述

预览输出 JSOI2019 Round 2 神经网络(neural) 神经网络(neural) 【题目背景】 火星探险队发现,火星人的思维方式与人类非常不同,是因为他们拥有与人类很不 一样的神经网络结构。为了更好地理解火星人的行为模式,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 中的其他节点一次且仅一次,并且回到第一棵树的第一个节点。 【输入格式】 从文件neural.in 中读入数据。 第一行读入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。 【输出格式】 输出到文件neural.out 中。 因为哈密顿回路的数量可能很多,你只需要输出一个非负整数,表示答案对998244353 取模后的值。 第5 页 共9 页

预览输出 JSOI2019 Round 2 神经网络(neural) 【样例1 输入】 1 2 2 3 3 1 2 4 1 3 5 2 6 1 2 【样例1 输出】 1 12 【样例1 解释】 在这个样例中, G 中一共有5 个点, 只有第一棵树的2, 3 节点之间没有边, 其他任 意两个点之间都存在边. 这样的图哈密顿回路个数为12. 【样例2】 见选手目录下的neural/neural2.in 与neural/neural2.ans。 【子任务】 测试点 ∑m i=1 ki m ki 树形态限制 1 ≤10 ≤3 无限制 无限制 2 ≤15 ≤4 3 ≤600 ≤300 ≤2 4,5,6 ≤900 ≤3 7,8,9,10 2, 500 50 50 11,12,13,14 ≤5, 000 ≤300 无限制 每棵树都是链 15,16,17,18,19,20 无限制 第6 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
3
1 2
1 3
2
1 2
12

样例 2

3
3
1 2
1 3
4
1 2
2 3
3 4
2
1 2
12336