直径集合

题目描述

给定一棵有 $N$ 个顶点的树。

顶点编号为 $1$、$2$、$\ldots$、$N$，对于每个 $1 \le i \le N-1$，第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$。

设 $D$ 为树的直径。求选出两个或两个以上顶点涂成红色，使得任意两个红色顶点之间的距离都等于 $D$ 的方案数，对 $998244353$ 取模。

这里，两个顶点之间的距离是指从一个顶点到达另一个顶点所需经过的最少边数，树的直径是任意两个顶点之间距离的最大值。

输入格式

输入按以下格式从标准输入给出：

$N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

输出格式

输出答案。

样例

5
1 2
1 3
1 4
4 5

2

给定的树有五个顶点，直径为 $3$。

距离为 $3$ 的顶点对只有两对：(2,5) 和 (3,5)，因此满足条件的涂色方案有两种：$\lbrace 2,5\rbrace$ 和 $\lbrace 3,5\rbrace$。

注意，将 2、3、5 涂成红色不满足条件，因为顶点 $2$ 和顶点 $3$ 之间的距离为 $2$。

4
1 2
1 3
1 4

4

直径为 $2$，满足条件的四种涂色方案为：$\lbrace 2,3\rbrace$、$\lbrace 2,4\rbrace$、$\lbrace 3,4\rbrace$、$\lbrace 2,3,4\rbrace$。

数据范围

• $2 \le N \le 2\times 10^5$
• $1 \le U_i, V_i \le N$
• $U_i \neq V_i$
• 输入均为整数。
• 给定的图是一棵树。