分数: 800 点
问题陈述
我们有一棵树 N 顶点,编号 1, \ldots, N。
对于每个 i=1,\ldots,N-1, i第一条边连接顶点 a_i 和顶点 b_i.
当每个顶点最多放置一个片段时,对该树的操作定义如下。
- 同时将每个棋子移动到与该棋子所占据的顶点相邻的顶点之一。
据说一个操作是 好 当满足以下条件时。
- 每条边最多被一个片段遍历。
- 操作后每个顶点最多被一个棋子占据。
高桥将在他选择的一个或多个顶点上放置一块。其中 2^N-1 放置棋子的方式,求满足以下条件的棋子的个数,取模 998244353.
- 对于每个非负整数 K,以下成立。
- 可以进行良好的操作 K 次。
- 让 S_K 是紧随其后的棋子所占据的顶点集 K 运营良好。然后, S_K 是独一无二的。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq a_i \lt b_i \leq N
- 给定的图是一棵树。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
输出
打印答案。
示例输入 1
3 1 2 1 3
示例输出 1
2
以下是满足条件的两种方法。
- 在顶点上放一块 1 和顶点 2.
- 在顶点上放一块 1 和顶点 3.
请注意,他必须在至少一个顶点上放置一块。
示例输入 2
7 1 2 1 3 2 4 2 5 3 6 3 7
示例输出 2
0
可能无法满足该条件。
示例输入 3
19 9 14 2 13 1 3 17 19 13 18 12 19 4 5 2 10 4 9 8 11 3 15 6 8 8 10 6 19 9 13 11 15 7 17 16 17
示例输出 3
100