题目描述

$1$ から $N$ までの番号がつけられた $N$ 個の頂点を持つ木 $G$ があります。 $G$ の $i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

$G$ に $0$ 本以上の辺を追加することを考えます。 追加後のグラフを $H$ とします。

以下の $4$ つの条件を満たす $H$ の個数を $998244353$ で割ったあまりを求めてください。

• $H$ に多重辺は存在しない
• $H$ に自己ループは存在しない
• $G$ の直径と $H$ の直径は等しい
• $H$ に辺が存在しない任意の頂点対について、$H$ にその頂点対間を結ぶ辺を追加すると、直径が短くなる

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

给定一棵 $N$ 个节点的树 $G$，你可以在 $G$ 上加若干条边形成图 $H$，要求图 $H$ 满足以下性质：

• 无重边自环；
• $H$ 的直径长度与 $G$ 的直径长度相同；
• 对于任何一对在 $H$ 上没有连边的点对 $(i,j)(i \neq j)$，连接 $(i,j)$ 后 $H$ 的直径变短。

求有多少种合法的 $H$，对 $998244353$ 取模。

6
1 6
2 1
5 2
3 4
2 3

3

3
1 2
2 3

1

9
1 2
2 3
4 2
1 7
6 1
2 5
5 9
6 8

27

19
2 4
15 8
1 16
1 3
12 19
1 18
7 11
11 15
12 9
1 6
7 14
18 2
13 12
13 5
16 13
7 1
11 10
7 17

78732

提示

制約

• $3\ \le\ N\ \le\ 2\ \times\ 10^5$
• $1\ \le\ a_i,\ b_i\ \le\ N$
• 入力で与えられるグラフは木

Sample Explanation 1

例えば、$G$ に辺 $(1,\ 5),\ (3,\ 5)$ を追加したグラフは問題文中の $4$ つの条件を満たします。

Sample Explanation 2

$H$ として考えられるグラフは、$G$ のみです。