← 返回题目列表

AtCoder · wtf22_day1_c

C. 缩小树

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

分数: 1500 点

问题陈述

你得到一棵树 T 与 N 顶点编号 1 to N。 的 i第一条边连接顶点 A_i 和 B_i.

您可以执行以下操作任意次数,可能为零。

  • 选择两片叶子 u 和 v of T 使它们之间的距离为奇数。然后,移除 u 和 v 来自 T (连同相关的边)。

在这里,当某个顶点在操作时的度正好为一时,该顶点被称为叶子。 两个顶点之间的距离是连接这两个顶点的路径中的边数。

求模数 998244353,可以作为顶点集的集合 T 操作后。

约束

  • 2 \leq N \leq 150
  • 1 \leq A_i,B_i \leq N
  • 输入图是一棵树。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

输出

打印答案。


示例输入 1

4
1 2
2 3
3 4

示例输出 1

3

执行零次操作会得到顶点集 \{1,2,3,4\}.

删除叶子 1 和 4 来自 T 会得到顶点集 \{2,3\}.

从这个状态开始,删除叶子 2 和 3 会得到顶点集 \{\}.


示例输入 2

5
2 1
3 1
4 1
5 3

示例输出 2

3

示例输入 3

8
2 1
3 2
4 1
5 2
6 5
7 3
8 7

示例输出 3

11

示例输入 4

24
12 7
14 4
8 13
24 13
1 3
4 9
17 2
1 21
24 22
11 1
15 17
22 5
23 10
24 12
13 6
12 16
10 21
19 22
20 17
4 20
20 6
10 18
21 6

示例输出 4

5359