分数: 600 点
问题陈述
有一棵树 N 顶点编号 1 to N。的 i第一条边连接顶点 u_i 和 v_i.
此外,还有 N 件编号 1 to N。最初,一块 i 放置在顶点上 i.
您可以执行以下操作任意次数,可能为零:
- 选择一条边。让顶点 u 和 v 是边的端点,并交换顶点上的碎片 u 和 v。然后,删除选定的边。
让 a_i 是顶点上的棋子 i。有多少种不同的可能序列 执行完操作后, (a_1, a_2, \dots, a_N) 是否存在?求计数模数 998244353.
约束
- 2 \leq N \leq 3000
- 1 \leq u_i \lt v_i \leq N
- 输入中给出的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
输出
打印数字,模数 998244353,可能的序列 (a_1, a_2, \dots, a_N).
示例输入 1
3 1 2 2 3
示例输出 1
5
例如,序列 (a_1, a_2, a_3) = (2, 1, 3) 可以通过以下步骤获取:
- 选择第一条边,交换顶点上的碎片 1 和 2,然后删除边缘。这导致 (a_1, a_2, a_3) = (2, 1, 3).
- 完成操作。
另外,序列 (a_1, a_2, a_3) = (3, 1, 2) 可以通过以下步骤获取:
- 选择第二条边,交换顶点上的碎片 2 和 3,然后删除边缘。这导致 (a_1, a_2, a_3) = (1, 3, 2).
- 选择第一条边,交换顶点上的碎片 1 和 2,然后删除边缘。这导致 (a_1, a_2, a_3) = (3, 1, 2).
- 完成操作。
该操作可以产生以下五个序列:
- (1, 2, 3)
- (1, 3, 2)
- (2, 1, 3)
- (2, 3, 1)
- (3, 1, 2)
示例输入 2
5 2 5 3 4 1 3 1 5
示例输出 2
34
示例输入 3
8 4 5 2 5 3 6 1 3 1 8 2 7 2 8
示例输出 3
799