Reunion

题意翻译

2050年大会即将举行 . 大会有 $n$ 个志愿者 , 他们之间的关系可以用一棵 $n$ 的点的树描述 . 第 $i$ 个结点代表第 $i$ 个志愿者 . 定义树上两点间距离 $\mathrm{dis}(u,v)$ 为为他们之间的最短路径所经过的边数 . 现在他们想进行一场聚会 , 一些志愿者有空参加 , 而其它的正忙 . 在这种情况下 , 对于某个志愿者 $x$ 和非负整数 $r$ , 如果所有与 $x$ 的距离不超过 $r$ 的志愿者**全部**有空参加 , 那么可以召开一场以 $x$ 为中心 , 半径为 $r$ 的聚会 . 这场聚会的等级定义为所有可能的半径 $r$ 中的**最大值** . 每一个志愿者都有 $\frac12$ 的概率有空参加或者正忙 . 现在请你求出所有情况下聚会等级的**期望**对 $998\ 244\ 353$ 取模的结果 . 特别的 , 当所有志愿者都正忙时 , 该聚会的等级为 $-1$ ; 当所有志愿者都有空参加时 , 该聚会的等级为 $n$ . ### 输入格式 第 $1$ 行一个整数 $n$ , 表示树的结点数目 . ( $2\leq n \leq 300$) 第 $2\sim n$ 行每行两个整数 $u,v$ , 表示树上的一条边 . ### 输出格式 一行内一个整数 , 表示聚会等级的期望对 $998\ 244\ 353$ 取模的结果 .

题目描述

It is reported that the 2050 Conference will be held in Yunqi Town in Hangzhou from April 23 to 25, including theme forums, morning jogging, camping and so on. The relationship between the $ n $ volunteers of the 2050 Conference can be represented by a tree (a connected undirected graph with $ n $ vertices and $ n-1 $ edges). The $ n $ vertices of the tree corresponds to the $ n $ volunteers and are numbered by $ 1,2,\ldots, n $ . We define the distance between two volunteers $ i $ and $ j $ , dis $ (i,j) $ as the number of edges on the shortest path from vertex $ i $ to vertex $ j $ on the tree. dis $ (i,j)=0 $ whenever $ i=j $ . Some of the volunteers can attend the on-site reunion while others cannot. If for some volunteer $ x $ and nonnegative integer $ r $ , all volunteers whose distance to $ x $ is no more than $ r $ can attend the on-site reunion, a forum with radius $ r $ can take place. The level of the on-site reunion is defined as the maximum possible radius of any forum that can take place. Assume that each volunteer can attend the on-site reunion with probability $ \frac{1}{2} $ and these events are independent. Output the expected level of the on-site reunion. When no volunteer can attend, the level is defined as $ -1 $ . When all volunteers can attend, the level is defined as $ n $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2\le n\le 300 $ ) denoting the number of volunteers. Each of the next $ n-1 $ lines contains two integers $ a $ and $ b $ denoting an edge between vertex $ a $ and vertex $ b $ .

输出格式

Output the expected level modulo $ 998\,244\,353 $ . Formally, let $ M = 998\,244\,353 $ . It can be shown that the answer can be expressed as an irreducible fraction $ \frac{p}{q} $ , where $ p $ and $ q $ are integers and $ q \not \equiv 0 \pmod{M} $ . Output the integer equal to $ p \cdot q^{-1} \bmod M $ . In other words, output such an integer $ x $ that $ 0 \le x < M $ and $ 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

说明

For the first example, the following table shows all possible outcomes. $ yes $ means the volunteer can attend the on-site reunion and $ no $ means he cannot attend. $ $\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} $ $ The expected level is $ \\frac{3+1+1+(-1)}{2^3}=\\frac{1}{2}$.