Diameter set

题目描述

给定一棵有 $N$ 个顶点的树。 顶点编号为 $1,2,\ldots,N$，并且对于每个 $1\leq i\leq N-1$，第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$。 令 $D$ 为这棵树的直径。求将两个或更多顶点选出并涂成红色的方法数（对 $998244353$ 取模），使得任意两个红色顶点之间的距离都是 $D$。 这里，两个顶点之间的距离是指从一个顶点到另一个顶点所需经过的最少边数，树的直径是任意两点之间距离的最大值。

输入格式

输入通过标准输入按如下格式给出： $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

4
1 2
1 3
1 4

4

提示

$2 \leq N \leq 2\times 10^5$ $1 \leq U_i,V_i \leq N$ $U_i \neq V_i$ 输入中的所有数值都是整数。 给定的图是一棵树。给定的树有五个顶点，直径为 $3$。
恰好有两对顶点的距离为 $3$：$(2,5)$ 和 $(3,5)$，因此满足条件的涂色方案有两种：$\lbrace 2,5\rbrace$ 和 $\lbrace 3,5\rbrace$。
注意将 $2,3,5$ 都涂成红色不满足条件，因为顶点 $2$ 和顶点 $3$ 之间的距离是 $2$。
直径是 $2$，满足条件的四种涂色方式是：$\lbrace 2,3\rbrace$、$\lbrace 2,4\rbrace$、$\lbrace 3,4\rbrace$、$\lbrace 2,3,4\rbrace$。

标签: AtCoder|abc221F

来源

AtCoder|abc221F