分数: 500 点
问题陈述
给定一棵树 N 顶点。 顶点已编号 1, 2, \ldots, N,并且对于每个 1\leq i\leq N-1, i第一条边连接顶点 U_i 和顶点 V_i。 让 D 是树的直径。求模数 998244353,选择两个或多个顶点并将它们涂成红色的方法,以便两个红色顶点之间的所有距离都是 D.
这里,两个顶点之间的距离是从一个顶点到另一个顶点必须遍历的最小边数,树的直径是两个顶点之间的最大距离。
约束
- 2 \leq N \leq 2\times 10^5
- 1 \leq U_i,V_i \leq N
- U_i \neq V_i
- 输入中的所有值都是整数。
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
输出
打印答案。
示例输入 1
5 1 2 1 3 1 4 4 5
示例输出 1
2
给定的树有五个顶点,直径为 3.
只有两对顶点,其距离为 3: (2,5) 和 (3,5),因此有两种方法来绘制树以满足条件: \lbrace 2,5\rbrace 和 \lbrace 3,5\rbrace .
注意画 2,3,5 不满足条件,因为顶点之间的距离 2 和顶点 3 is 2.
示例输入 2
4 1 2 1 3 1 4
示例输出 2
4
直径为 2,满足条件的绘制树的四种方法是: \lbrace 2,3\rbrace , \lbrace 2,4\rbrace , \lbrace 3,4\rbrace , \lbrace 2,3,4\rbrace .