据悉,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}$$$。