[AGC058F] Authentic Tree DP

对于一棵无向树 $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$。

[problemUrl]: https://atcoder.jp/contests/agc058/tasks/agc058_f 無向木 $ 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} $

答えを出力せよ．

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 $ です．