← 返回题目列表

Codeforces · 1517/F

F. 团聚

中文机器翻译题面 查看原题

据悉,2050大会将于4月23日至25日在杭州云栖小镇举行,包括主题论坛、晨跑、露营等。

2050 年大会的 $$$n$$$ 志愿者之间的关系可以用树来表示(具有 $$$n$$$ 个顶点和 $$$n-1$$$ 个边的连通无向图)。树的 $$$n$$$ 顶点对应于 $$$n$$$ 志愿者,编号为 $$$1,2,\ldots, n$$$。

我们定义两个志愿者 $$$i$$$ 和 $$$j$$$ 之间的距离,dis$$$(i,j)$$$ 为树上从顶点 $$$i$$$ 到顶点 $$$j$$$ 的最短路径上的边数。每当 $$$i=j$$$ 时,dis$$$(i,j)=0$$$。

部分志愿者可以参加现场聚会,部分志愿者则不能参加。如果对于某个志愿者$$$x$$$和非负整数$$$r$$$,与$$$x$$$距离不超过$$$r$$$的所有志愿者都可以参加现场聚会,则可以举办半径为$$$r$$$的论坛。现场聚会的级别被定义为任何可以举行的论坛的最大可能半径。

假设每个志愿者可以以 $$$\frac{1}{2}$$$ 的概率参加现场聚会,并且这些事件是独立的。输出现场团聚的预期水平。当没有志愿者可以参加时,级别定义为$$$-1$$$。当所有志愿者都可以参加时,级别定义为$$$n$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$2\le n\le 300$$$) 表示志愿者的数量。

接下来的 $$$n-1$$$ 行包含两个整数 $$$a$$$ 和 $$$b$$$ ,表示顶点 $$$a$$$ 和顶点 $$$b$$$ 之间的边。

输出

输出对 $$$998\,244\,353$$$ 取模的预期级别。

正式地,令 $$$M = 998\,244\,353$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

示例

输入 #1

3
1 2
2 3

输出 #1

499122177

输入 #2

5
1 2
2 3
3 4
3 5

输出 #2

249561089

输入 #3

10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

输出 #3

821796866

注意

对于第一个示例,下表显示了所有可能的结果。 $$$yes$$$表示志愿者可以参加现场聚会,$$$no$$$表示不能参加。 $$$$$$\begin{array}{cccc} 1 & 2 & 3 & level\\ yes & yes & yes & 3\\ yes & yes & no & 1\\ yes & no & yes & 0\\ yes & no & no & 0\\ no & yes & yes & 1\\ no & yes & no & 0\\ no & no & yes & 0\\ no & no & no & -1\\ \end{array}$$$$$$ 预期级别为$$$\frac{3+1+1+(-1)}{2^3}=\frac{1}{2}$$$。