← 返回题目列表

AtCoder · arc130_d

D. 之字形树

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给定一棵树 N 顶点。顶点已编号 1 to N,以及 i第一条边连接顶点 a_i 和 b_i.

求正整数序列的个数 P = (P_1, P_2, \ldots, P_N) 满足以下条件,模 998244353.

  • 1\leq P_i\leq N
  • P_i\neq P_j if i\neq j.
  • 对于 1\leq a, b, c\leq N,如果顶点 a 和 b 相邻,并且顶点 b 和 c 也相邻, P_a < P_b > P_c or 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

的 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