D - Deterministic Placing 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 800 点

問題文

N 頂点の木があり、各頂点には 1,\ldots,N と番号が付けられています。 i=1,\ldots,N-1 に対し、 i 番目の辺は頂点 a_i と頂点 b_i を結びます。
この木の各頂点に高々 1 個の駒が置かれた状態に対する操作を次のように定めます。

  • すべての駒を、同時に、隣接する頂点のうちの 1 つへ移動させる。

また、以下の条件を満たす操作を 良い操作 と呼びます。

  • すべての辺について、その辺を通して移動する駒は高々 1 個である。
  • 操作後に各頂点に置かれている駒は高々 1 個である。

高橋君は 1 個以上の頂点を選び、駒を 1 個ずつ置くことにしました。 駒を置く方法は 2^N-1 通りありますが、そのうち次の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • すべての非負整数 K について以下の条件を満たす。
    • 良い操作を K 回行うことができる。
    • 良い操作を K 回行った時点で駒が置かれている頂点の集合を S_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

次の 2 通りが条件を満たします。

  • 頂点 1 と頂点 2 を選び、駒を置く。
  • 頂点 1 と頂点 3 を選び、駒を置く。

頂点を 1 個以上選ぶ必要があることに気を付けてください。

入力例 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

Score : 800 points

Problem Statement

We have a tree with N vertices, numbered 1, \ldots, N. For each i=1,\ldots,N-1, the i-th edge connects Vertex a_i and Vertex b_i.
An operation on this tree when at most one piece is put on each vertex is defined as follows.

  • Simultaneously move every piece to one of the vertices adjacent to the one occupied by the piece.

An operation is said to be good when the conditions below are satisfied.

  • Each edge is traversed by at most one piece.
  • Each vertex will be occupied by at most one piece after the operation.

Takahashi will put a piece on one or more vertices of his choice. Among the 2^N-1 ways to put pieces, find the number of ones that satisfy the condition below, modulo 998244353.

  • For every non-negative integer K, the following holds.
    • It is possible to perform a good operation K times.
    • Let S_K be the set of vertices occupied by pieces just after K good operations. Then, S_K is unique.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq a_i \lt b_i \leq N
  • The given graph is a tree.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

Output

Print the answer.

Sample Input 1

3
1 2
1 3

Sample Output 1

2

Here are the two ways to satisfy the condition.

  • Put a piece on Vertex 1 and Vertex 2.
  • Put a piece on Vertex 1 and Vertex 3.

Note that he must put a piece on at least one vertex.

Sample Input 2

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

Sample Output 2

0

There might be no way to satisfy the condition.

Sample Input 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

Sample Output 3

100