分数: 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