You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
小 D 不是 OP!(genshin)
众所周知,小 D 不是 OP,所以小 I 在玩原神的时候只会跑图开宝箱。
原神地图可以视作为 m 个国家,每个国家 i 包含个 ki 城市,一个国家之间通过 ki−1 条道路把所有城市相连,不同国家的城市之间没有道路。
小 I 一开始在 1 号国家的城市 1。小 I 想要经过 k1+k2+⋯+km 时刻之后遍历所有国家的所有城市再回到起点。小 I 可以通过花费 1 时刻从 u 到达 v 当且仅当:u,v 通过道路相连,或者 u,v 处于不同国家(这样小 i 就会使用传送锚点)。
你需要告诉小 I 他有多少种方案遍历所有城市。答案对 998244353 取模。
输入格式
第一行一个正整数 m 表示国家数目。
对于每个国家,第一行一个 ki 表示城市数目。
接下来 ki−1 行,每行两个正整数 uj,vj 描述一条这个国家的道路(uj,vj∈[1,ki])。
输出格式
对每个测试点输出一个正整数表示答案。
测试样例
样例输入 |
样例输出 |
2121 2 |
2 |
见下发 genshin/genshin2.in |
见下发 genshin/genshin2.ans |
见下发 genshin/genshin3.in |
见下发 genshin/genshin3.ans |
见下发 genshin/genshin4.in |
见下发 genshin/genshin4.ans |
样例解释
假设 (x,y) 表示第 x 个国家的第 y 个城市。那么样例 1 有两种方案:
(1,1)→(2,1)→(2,2)→(1,1),(1,1)→(2,2)→(2,1)→(1,1)。
样例 2 满足测试点 1 的限制。
样例 3 满足测试点 7,14 的限制。
样例 4 满足测试点 15 的限制。
数据范围
对所有数据,有 m≤300,∑ki≤5000。
测试点编号 |
∑ki≤ |
m≤ |
ki≤ |
国家道路的形态 |
1 |
10 |
3 |
10 |
无 |
2 |
15 |
4 |
3 |
600 |
300 |
2 |
4∼6 |
900 |
3 |
7∼10 |
2500 |
50 |
11∼14 |
5000 |
300 |
5000 |
每个国家道路都是链 |
15∼20 |
无 |
时间限制:1s。
空间限制:512MB。