UOJ Logo Universal Online Judge

UOJ

#351. 新年的叶子

统计

躲过了AlphaGo之后,你躲在SingleDog的长毛里,和它们一起来到了AlphaGo的家。此时你们才突然发现,AlphaGo的家居然是一个隐藏在地下的计算中心!难道AlphaGo如此人赢的秘密是...它其实是一个AI?

根据情报,这个地下的计算中心的结构构成了一棵无根树,整个计算中心名为被AT-field的力场保护起来,保护力场的直径恰好等于树的直径(树的直径定义为树上距离最远的两个结点之间的距离,结点 $u,v$ 的距离定义为从 $u$ 到 $v$ 最少需要经过的边数)。

由于保护力场的存在,SingleDog们每次只能进入整棵树的一个叶子(度为1的结点),由于狗的大脑很小,他们每次只会随机进攻一个原树的叶子,并且破坏里面的设备,更加狼狈的是他们甚至会重复进入一个已经被破坏过的叶子。

一棵树

比如这棵树中,SingleDog们攻击的就是${3,4,7}$这三个点,他们不会攻击$2$号点,因为它不是原树的叶子。

他们想知道,期望多少次之后,可以使得保护力场的直径缩小?

即,对于一棵树,每次随机染黑一个叶子(可能会重复染黑),期望多少次后直径变小?

输入格式

从标准输入读入数据。

第一行一个正整数$n$,表示树的点数。

接下来$n-1$行,每行两个正整数$x,y$,表示树上的一条边。

输出格式

输出到标准输出。

输出一行一个整数表示答案在模 $998244353$ 意义下的取值。

即设答案化为最简分式后的形式为 $\frac{a}{b}$ ,其中 $a$ 和 $b$ 互质。输出整数 $x$ 使得 $bx\equiv a \pmod{998244353}$且 $0\le x < 998244353$。可以证明这样的整数 $x$ 是唯一的。

样例一

input

3
1 2
2 3

output

1

样例二

input

6
1 2
2 3
1 4
4 5
1 6

output

499122178

样例三

见样例数据下载。

样例四

见样例数据下载。

限制与约定

对于所有数据,$3 \le n \le 5\times10^5$,$1\le x,y\le n$。

为了拿到每个子任务的分数,你必须通过所有他依赖的子任务。

子任务 分值 $n$ 特殊性质 依赖的subtask
1 12 $\le 10$
2 18 $\le 3\times 10^3$ $1$
3 20 $\le 5\times 10^5$ 树上任意两点距离(距离定义为两点间最短路边的条数)$\le 3$
4 15 $\le 5\times 10^5$ 任意点度数$\le 3$
5 35 $\le 5\times 10^5$ $1,2,3,4$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载