← 返回题目列表

AtCoder · hitachi2020_f

F. 保留直径

中文机器翻译题面 查看原题

分数: 1100 点

问题陈述

我们有一棵树 G 与 N 顶点编号 1 to N。 的 i第边缘 G 连接顶点 a_i 和顶点 b_i.

考虑添加零个或多个边 G,让 H 是结果图。

查找图表的数量 H 满足以下条件,模 998244353.

  • H 不包含自循环或多重边。
  • 的直径 G 和 H 相等。
  • 对于每对顶点 H 不是通过边直接连接的,添加直接连接它们的边会减小图的直径。

约束

  • 3 \le N \le 2 \times 10^5
  • 1 \le a_i, b_i \le N
  • 给定的图是一棵树。

输入

输入由标准输入按以下格式给出:

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

输出

打印答案。


示例输入 1

6
1 6
2 1
5 2
3 4
2 3

示例输出 1

3

例如,添加边缘 (1, 5), (3, 5) in G 满足条件。


示例输入 2

3
1 2
2 3

示例输出 2

1

唯一的图 满足条件的 H 是 G.


示例输入 3

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

示例输出 3

27

示例输入 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