C - Swap on Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

頂点に 1 から N までの番号がついた N 頂点の木があります。i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。
また、1 から N までの番号がついた N 個の駒があります。はじめ駒 i は頂点 i に置かれています。
あなたは次の操作を 0 回以上好きな回数行うことができます。

  • 辺を 1 本選ぶ。辺の両端点を頂点 u, v として、頂点 u に載っている駒と頂点 v に載っている駒を入れ替える。その後、選んだ辺を削除する。

頂点 i に載っている駒を a_i とします。操作を全て終了した時点における数列 (a_1, a_2, \dots, a_N) としてあり得るものは何個ありますか？答えを 998244353 で割った余りを求めてください。

制約

  • 2 \leq N \leq 3000
  • 1 \leq u_i \lt v_i \leq N
  • 入力で与えられるグラフは木

入力

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

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

出力

(a_1, a_2, \dots, a_N) としてあり得るものの個数を 998244353 で割った余りを出力せよ。

入力例 1

3
1 2
2 3

出力例 1

5

例えば以下の手順により (a_1, a_2, a_3) = (2, 1, 3) を得ることが出来ます。

  • 1 番目の辺を選び、頂点 1 と頂点 2 に載っている駒を入れ替えて辺を削除する。(a_1, a_2, a_3) = (2, 1, 3) になる。
  • 操作を終了する。

また、以下の手順により (a_1, a_2, a_3) = (3, 1, 2) を得ることが出来ます。

  • 2 番目の辺を選び、頂点 2 と頂点 3 に載っている駒を入れ替えて辺を削除する。(a_1, a_2, a_3) = (1, 3, 2) になる。
  • 1 番目の辺を選び、頂点 1 と頂点 2 に載っている駒を入れ替えて辺を削除する。(a_1, a_2, a_3) = (3, 1, 2) になる。
  • 操作を終了する。

操作によって得られる数列は次の 5 通りです。

  • (1, 2, 3)
  • (1, 3, 2)
  • (2, 1, 3)
  • (2, 3, 1)
  • (3, 1, 2)

入力例 2

5
2 5
3 4
1 3
1 5

出力例 2

34

入力例 3

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

出力例 3

799

Score: 600 points

Problem Statement

There is a tree with N vertices numbered 1 to N. The i-th edge connects vertices u_i and v_i.
Additionally, there are N pieces numbered 1 to N. Initially, piece i is placed on vertex i.
You can perform the following operation any number of times, possibly zero:

  • Choose one edge. Let vertices u and v be the endpoints of the edge, and swap the pieces on vertices u and v. Then, delete the chosen edge.

Let a_i be the piece on vertex i. How many different possible sequences (a_1, a_2, \dots, a_N) exist when you finish performing the operation? Find the count modulo 998244353.

Constraints

  • 2 \leq N \leq 3000
  • 1 \leq u_i \lt v_i \leq N
  • The graph given in the input is a tree.

Input

The input is given from Standard Input in the following format:

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Print the number, modulo 998244353, of possible sequences (a_1, a_2, \dots, a_N).

Sample Input 1

3
1 2
2 3

Sample Output 1

5

For example, the sequence (a_1, a_2, a_3) = (2, 1, 3) can be obtained by the following steps:

  • Choose the first edge, swap the pieces on vertices 1 and 2, and delete the edge. This results in (a_1, a_2, a_3) = (2, 1, 3).
  • Finish operating.

Also, the sequence (a_1, a_2, a_3) = (3, 1, 2) can be obtained by the following steps:

  • Choose the second edge, swap the pieces on vertices 2 and 3, and delete the edge. This results in (a_1, a_2, a_3) = (1, 3, 2).
  • Choose the first edge, swap the pieces on vertices 1 and 2, and delete the edge. This results in (a_1, a_2, a_3) = (3, 1, 2).
  • Finish operating.

The operation can yield the following five sequences:

  • (1, 2, 3)
  • (1, 3, 2)
  • (2, 1, 3)
  • (2, 3, 1)
  • (3, 1, 2)

Sample Input 2

5
2 5
3 4
1 3
1 5

Sample Output 2

34

Sample Input 3

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

Sample Output 3

799