F - Authentic Tree DP 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 2000 点

問題文

無向木 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 < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。

制約

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

入力

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

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

出力

答えを出力せよ．

入力例 1

2
1 2

出力例 1

499122177

f(T)=1/2 です．

入力例 2

3
1 2
2 3

出力例 2

332748118

f(T)=1/3 です．

入力例 3

4
1 2
2 3
3 4

出力例 3

103983787

入力例 4

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

出力例 4

462781191

Score : 2000 points

Problem Statement

For an undirected tree t, let us define a rational number f(t) as follows.

  • Let n be the number of vertices in t.
  • If n=1: Let f(t)=1.
  • If n \geq 2:
    • For an edge e in t, we denote by t_x(e) and t_y(e) the two trees that result from deleting e from t (in arbitrary order).
    • Let f(t)=(\sum_{e \in t} f(t_x(e)) \times f(t_y(e)))/n.

You are given a tree T with N vertices numbered 1 to N. The i-th edge connects Vertex A_i and Vertex B_i.

Find the value f(T) \text{mod }{998244353}.

What is a rational number \text{mod }{998244353}?

Under the Constraints of this problem, when the sought rational number is represented as \frac{P}{Q}, it can be proved that Q \neq 0 \pmod{998244353}. Therefore, there is a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Find this R.

Constraints

  • 2 \leq N \leq 5000
  • 1 \leq A_i,B_i \leq N
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

2
1 2

Sample Output 1

499122177

We have f(T)=1/2.

Sample Input 2

3
1 2
2 3

Sample Output 2

332748118

We have f(T)=1/3.

Sample Input 3

4
1 2
2 3
3 4

Sample Output 3

103983787

Sample Input 4

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

Sample Output 4

462781191