AT_abc221_f [ABC221F] Diameter set

题目描述

给定一棵有 $N$ 个顶点的树。顶点编号为 $1, 2, \ldots, N$，对于 $1 \leq i \leq N-1$，第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$。设这棵树的直径为 $D$，请计算有多少种方法可以选择至少 $2$ 个顶点并将它们染成红色，使得任意两个被染红的顶点之间的距离都等于 $D$。请将答案对 $998244353$ 取模后输出。

其中，树上两个顶点之间的距离是指从一个顶点到另一个顶点所经过的最少边数。树的直径定义为任意两个顶点之间距离的最大值。

输入格式

输入以以下格式从标准输入读入。

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

输出格式

输出答案。

输入输出样例 #1

输入 #1

5
1 2
1 3
1 4
4 5

输出 #1

2

输入输出样例 #2

输入 #2

4
1 2
1 3
1 4

输出 #2

4

说明/提示

限制条件

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

样例解释 1

给定的树有 $5$ 个顶点，直径为 $3$。距离为 $3$ 的顶点对只有 $(2,5)$ 和 $(3,5)$，因此满足条件的染色方法只有 $\lbrace 2,5\rbrace$ 和 $\lbrace 3,5\rbrace$ 共 $2$ 种。注意，$\lbrace 2,3,5\rbrace$ 不满足条件，因为顶点 $2$ 和顶点 $3$ 之间的距离为 $2$。

样例解释 2

直径为 $2$，满足条件的染色方法有 $\lbrace 2,3\rbrace$、$\lbrace 2,4\rbrace$、$\lbrace 3,4\rbrace$、$\lbrace 2,3,4\rbrace$ 共 $4$ 种。

由 ChatGPT 4.1 翻译