题目描述

$N$ 頂点からなる木が与えられます。 頂点は $1$ , $2$ , $\ldots$ , $N$ と番号付けられており、 $1\leq\ i\leq\ N-1$ について、$i$ 本目の辺は頂点 $U_i$ と頂点 $V_i$ を結んでいます。 木の直径を $D$ とするとき、木の頂点のうち $2$ 点以上を選んで赤く塗る方法であって、 赤く塗られたどの頂点の間の距離も $D$ であるようなものの数を $998244353$ で割った余りを求めてください。

ただし、木の $2$ 頂点の間の距離は一方から他方へ移動するときに用いる辺の本数の最小値であり、 木の直径は任意の $2$ 頂点の間の距離の最大値として定められます。

输入格式

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

$N$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_{N-1}$ $V_{N-1}$

输出格式

答えを出力せよ。

题目大意

给你一个 $n$ 个顶点的无根树, 记 $d$ 为它的直径.

求使得顶点集合 $S$ 中任意两个顶点的距离为 $d$ 的集合个数, 对 $998244353$ 取模.

$S$ 中至少要有两个数.

$n \le 2 \times 10^5$.

5
1 2
1 3
1 4
4 5

2

4
1 2
1 3
1 4

4

提示

制約

• $2\ \leq\ N\ \leq\ 2\times\ 10^5$
• $1\ \leq\ U_i,V_i\ \leq\ N$
• $U_i\ \neq\ V_i$
• 入力は全て整数である。
• 与えられるグラフは木である。

Sample Explanation 1

与えられた木は $5$ 頂点からなり、直径は $3$ です。 $2$ 頂点の組であって、その間の距離が $3$ であるようなものは $(2,5)$ , $(3,5)$ しか存在しないため、 条件をみたす塗り方は $\lbrace\ 2,5\rbrace$ と $\lbrace\ 3,5\rbrace$ の $2$ 通りとなります。 $\lbrace\ 2,3,5\rbrace$ は頂点 $2$ と頂点 $3$ の間の距離が $2$ であるため条件をみたさないことに注意してください。

Sample Explanation 2

直径は $2$ であり、条件をみたす塗り方は $\lbrace\ 2,3\rbrace$ , $\lbrace\ 2,4\rbrace$ , $\lbrace\ 3,4\rbrace$ , $\lbrace\ 2,3,4\rbrace$ の $4$ 通りとなります。