You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小仓鼠和他的基（mei）友（zi）sugar 住在地下洞穴中，每个节点的编号为 $1\sim n$ 间的一个整数。地下洞穴是一个树形结构（两个洞穴间距离为 $1$）。这一天小仓鼠打算从从他的卧室 $a$（是任意的）走到他的基友卧室 $b$（还是任意的）（注意，$a$ 有可能等于 $b$）。然而小仓鼠学 OI 学傻了，不知道怎么怎么样才能用最短的路程走到目的地，于是他只能随便乱走。当他在一个节点时，会等概率走到这个点的母亲或者所有孩子节点（例如这个节点有一个母亲节点和两个子节点，那么下一步走到这 $3$ 个节点的概率都是 $\dfrac{1}{3}$），一旦走到了他基友的卧室，就会停下。

现在小仓鼠希望知道，他走到目的地时，走的步数的期望。这个期望本来是一个有理数，但是为了避免误差，我们要求输出这个有理数对 $998,244,353$ 取模的结果。

形式化地说，可以证明答案可以被表示为既约分数 $\dfrac{y}{x}$，其中 $x\not\equiv 0\pmod {998,244,353}$。可以证明存在一个唯一的整数 $z$（$0\le z\lt 998,244,353$），使得 $xz=y$，你只需要输出 $z$ 的值。

小仓鼠那么弱，还要天天被 JOHNKRAM 大爷虐，请你快来救救他吧！

输入格式

第一行一个正整数 $n$，表示这棵树节点的个数。

接下来 $n-1$ 行，每行两个正整数 $u$ 和 $v$，表示节点 $u$ 到节点 $v$ 之间有一条边。

输出格式

一个整数，表示取模后的答案。

3
1 2
1 3

110916041

提示

样例解释：期望的真实值为 $\dfrac {16}{9}$。

如果 $a$ 是叶子，$b$ 是根，此时期望 $\mathbb{E}_1=1$，有 $2$ 种情况。

如果 $a$ 是根，$b$ 是叶子，则 $\displaystyle \mathbb{E}_2=\frac{1}{2}+\frac{3}{4}+\frac{5}{8}+\cdots=3$。有 $2$ 种情况。

如果 $a,b$ 是不同的叶子，则 $\mathbb{E}_3=\mathbb{E}_2+1=4$。有 $2$ 种情况。

如果 $a=b$，则 $\mathbb{E}_4=0$。有 $3$ 种情况。

所以答案为 $\displaystyle \frac{2\times 1+2\times 3+2\times 4+3\times 0}{2+2+2+3}=\frac{16}{9}$。

由于 $110,916,041\times 9=998,244,369\equiv 16\pmod {998,244,353}$，所以输出 $110,916,041$。

对于 $30\%$ 的数据，$n\le 5$；

对于 $50\%$ 的数据，$n\le 5000$；

对于所有数据，$n\le 100000$。

$\text{Statement fixed by @Starrykiller.}$