← 返回题目列表

AtCoder · arc142_d

D. 确定性放置

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

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