题目描述

$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$ は一意に定まる。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

给定一棵 $N$ 个点的树。初始时可以在某些节点上放置一颗棋子，且放置的棋子总数至少为 $1$，则共有 $2^N -1$ 种放置方案。

定义一次操作为，

• 对于每颗棋子，将其沿着树边移动到与当前节点相邻的一个节点上。

在一次操作内，所有棋子的移动是同时进行的，并且需要遵循以下规则。

• 每条树边最多被一颗棋子经过。

• 移动后每个节点上至多有一颗棋子。

现在你需要统计 $2^N-1$ 种放置方案中，满足以下条件的方案数，对 $998244353$ 取模。

• 对于每个非负整数 $K$，满足以下条件。
  • 至少能进行 $K$ 次操作。
  • 无论如何进行这 $K$ 次操作，最终所有棋子占据的节点集合唯一。

$2 \le N \le 2 \times 10^5$ 。

3
1 2
1 3

2

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

0

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

100

提示

制約

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ a_i\ \lt\ b_i\ \leq\ N$
• 与えられるグラフは木である
• 入力はすべて整数

Sample Explanation 1

次の $2$ 通りが条件を満たします。 - 頂点 $1$ と頂点 $2$ を選び、駒を置く。 - 頂点 $1$ と頂点 $3$ を選び、駒を置く。 頂点を $1$ 個以上選ぶ必要があることに気を付けてください。

Sample Explanation 2

条件を満たす駒の置き方が存在しない場合があります。