A - Paint Tree 2
問題文
頂点に $1$ から $N$ までの番号が付いた $N$ 頂点の木が与えられます。$i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結びます。はじめ、すべての頂点は白く塗られています。
$2$ つの端点がともに白く塗られているような辺がなくなるまで、以下の操作を繰り返し行います。
- $N$ 個の頂点から一様ランダムに頂点を $1$ つ選ぶ。選んだ頂点が白く塗られているならば、これを黒く塗る。そうでなければ何もしない。
操作を行う回数の期待値を$\bmod ~ 998244353$ で求めてください。
期待値を$\bmod \, 998244353$ で求めるとは？
本問題の制約下において、答えとなる期待値は必ず有理数となることを証明できます。さらに、求める値を互いに素な $2$ つの非負整数 $P, Q$ を用いて $\frac{P}{Q}$ と表したとき、$R \times Q \equiv P\mod 998244353$ かつ $0 \leq R < 998244353$ を満たす整数 $R$ がただ一つ存在することを証明できます。このような $R$ を求めて出力してください。
制約
- $2 \leq N \leq 2000$
- $1 \leq A_i, B_i \leq N$
- 与えられるグラフは木である
- 入力はすべて整数である
部分点
set1$(30$ 点$)$：$N \leq 18$all$(70$ 点$)$：追加の制約はない
入力
入力は以下の形式で標準入力から与えられます。
$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$
出力
答えを出力してください。
3
1 2
1 3
2
操作の一例を示します。
まず、頂点 $2$ が選ばれたとすると、この時点で頂点 $2$ は白いため黒く塗ります。$2$ 番目の辺について、頂点 $1$ も頂点 $3$ も白く塗られているため操作を続けて行います。
次に、頂点 $2$ が選ばれたとすると、この時点で頂点 $2$ は黒いため何もしません。$2$ 番目の辺について、頂点 $1$ も頂点 $3$ も白く塗られているため操作を続けて行います。
次に、頂点 $3$ が選ばれたとすると、この時点で頂点 $3$ は白いため黒く塗ります。$2$ つの端点がともに白く塗られているような辺がないため、操作を終了します。
この例では、操作を $3$ 回行います。
この入力例は部分点 set1 の制約を満たします。
2
1 2
1
この入力例は部分点 set1 の制約を満たします。
7
3 2
5 3
3 4
6 5
7 5
1 3
49912225
この入力例は部分点 set1 の制約を満たします。