分数: 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