← 返回题目列表

AtCoder · arc171_c

C. 在树上交换

中文机器翻译题面 查看原题

分数: 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