题目描述

無向木 $t$ に対して，有理数 $f(t)$ を次のように定義します．

• $t$ の頂点数を $n$ とする．
• $n=1$ のとき：$f(t)=1$ とする．
• $n\ \geq\ 2$ のとき：
  • $t$ の辺 $e$ について，$t$ から $e$ を削除することで得られる $2$ つの木を $t_x(e),t_y(e)$ （順不同）で表す．
  • $ f(t)=(\sum_{e\ \in\ t}\ f(t_x(e))\ \times\ f(t_y(e)))/n $ とする．

$1$ から $N$ までの番号のついた $N$ 頂点からなる木 $T$ が与えられます． $i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結ぶ辺です．

$f(T)$ の値を $\text{mod\ }{998244353}$ で求めてください．

有理数 $\text{mod\ }{998244353}$ の定義 この問題の制約のもとでは、求める有理数を既約分数 $\frac{P}{Q}$ で表した時、$Q\ \neq\ 0\ \pmod{998244353}$ となることが証明できます。 よって、$ R\ \times\ Q\ \equiv\ P\ \pmod{998244353},\ 0\ \leq\ R\ &lt\ 998244353 $ を満たす整数 $R$ が一意に定まります。 この $R$ を答えてください。

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_{N-1}$ $B_{N-1}$

输出格式

答えを出力せよ．

题目大意

对于一棵无向树 $t$，我们按如下方式定义有理数 $f(t)$：

• 令 $n$ 为 $t$ 的节点个数。
• 若 $n=1$：$f(t) = 1$。
• 若 $n>1$：
  • 对于 $t$ 内的一条边 $e$，我们定义 $t_x(e)$ 与 $t_y(e)$ 为从 $t$ 中删除 $e$ 得到的两棵子树（顺序任意）。
  • $f(t) = \left(\sum_{e\in t} f(t_x(e)) \times f(t_y(e))\right)/n$。

给定一棵 $n$ 个节点的树 $T$，节点编号自 $1$ 至 $n$。第 $i$ 条边链接了 $(a_i,b_i)$。

请输出 $f(T) \bmod 998244353$ 的值。

可以证明在满足题设的情况下，答案可以被表示为分数 $\frac PQ$。$\frac PQ \bmod 998244353$ 的结果为一个整数 $R$，满足 $Q\times R\equiv P\pmod {998244353}$。你需要输出的值即为 $R$。

$2\le n\le 5000$。

2
1 2

499122177

3
1 2
2 3

332748118

4
1 2
2 3
3 4

103983787

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

462781191

提示

制約

• $2\ \leq\ N\ \leq\ 5000$
• $1\ \leq\ A_i,B_i\ \leq\ N$
• 入力されるグラフは木である

Sample Explanation 1

$f(T)=1/2$ です．

Sample Explanation 2

$f(T)=1/3$ です．