D - Zigzag Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点からなる木が与えられます。頂点には 1 から N までの番号がついており、i 番目の辺は頂点 a_i と b_i を結んでいます。

正整数列 P = (P_1, P_2, \ldots, P_N) であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • 1\leq P_i\leq N
  • i\neq j ならば P_i\neq P_j
  • 1\leq a, b, c\leq N に対して頂点 a と 頂点 b、頂点 b と頂点 c がともに隣接しているならば、P_a < P_b > P_c または P_a > P_b < P_c が成り立つ。

制約

  • 2\leq N\leq 3000
  • 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

3
1 2
2 3

出力例 1

4

条件を満たす P は以下の 4 通りです。

  • P = (1, 3, 2)
  • P = (2, 1, 3)
  • P = (2, 3, 1)
  • P = (3, 1, 2)

入力例 2

4
1 2
1 3
1 4

出力例 2

12

入力例 3

6
1 2
2 3
3 4
4 5
5 6

出力例 3

122

入力例 4

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

出力例 4

19080

Score : 600 points

Problem Statement

Given is a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertices a_i and b_i.

Find the number of sequences of positive integers P = (P_1, P_2, \ldots, P_N) that satisfy the conditions below, modulo 998244353.

  • 1\leq P_i\leq N
  • P_i\neq P_j if i\neq j.
  • For 1\leq a, b, c\leq N, if Vertices a and b are adjacent, and Vertices b and c are also adjacent, P_a < P_b > P_c or P_a > P_b < P_c holds.

Constraints

  • 2\leq N\leq 3000
  • 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 answers.

Sample Input 1

3
1 2
2 3

Sample Output 1

4

The 4 sequences satisfying the conditions are:

  • P = (1, 3, 2)
  • P = (2, 1, 3)
  • P = (2, 3, 1)
  • P = (3, 1, 2)

Sample Input 2

4
1 2
1 3
1 4

Sample Output 2

12

Sample Input 3

6
1 2
2 3
3 4
4 5
5 6

Sample Output 3

122

Sample Input 4

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

Sample Output 4

19080