题目描述

有一棵包含 $N$ 个顶点的树 $G$，顶点编号为 $1$ 到 $N$。$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}$

输出格式

输出答案。

输入输出样例 #1

输入 #1

6
1 6
2 1
5 2
3 4
2 3

输出 #1

3

输入输出样例 #2

输入 #2

3
1 2
2 3

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

27

输入输出样例 #4

输入 #4

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

输出 #4

78732

说明/提示

限制条件

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq a_i, b_i \leq N$
• 输入给出的图是树

样例解释 1

例如，向 $G$ 添加边 $(1, 5)$、$(3, 5)$ 得到的图满足题目中的 $4$ 个条件。

样例解释 2

作为 $H$ 的图只有 $G$ 本身。

由 ChatGPT 4.1 翻译