F - 直径集合

得分: $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}$

输出

输出答案。

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 $。