#P13678. [ARC130D] Zigzag Tree

    ID: 12880 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-树形 DP前缀和优化 DP阶乘逆元预处理对称性分析

[ARC130D] Zigzag Tree

题目描述

给定一棵有 NN 个顶点的树。顶点编号为 11 到 NN,第 ii 条边连接顶点 aia_i 和 bib_i。

请计算满足以下条件的正整数序列 P=(P1,P2,…,PN)P = (P_1, P_2, \ldots, P_N) 的个数,并将结果对 998244353998244353 取模。

  • 1≤Pi≤N1 \leq P_i \leq N
  • 如果 i≠ji \neq j,则 Pi≠PjP_i \neq P_j
  • 对于任意 1≤a,b,c≤N1 \leq a, b, c \leq N,如果顶点 aa 和顶点 bb 相邻,且顶点 bb 和顶点 cc 也相邻,则有 Pa<Pb>PcP_a < P_b > P_c 或 Pa>Pb<PcP_a > P_b < P_c。

输入格式

输入以如下格式从标准输入读入。

NN
a1a_1 b1b_1
a2a_2 b2b_2
⋮\vdots
aN−1a_{N-1} bN−1b_{N-1}

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
1 2
2 3

输出 #1

4

输入输出样例 #2

输入 #2

4
1 2
1 3
1 4

输出 #2

12

输入输出样例 #3

输入 #3

6
1 2
2 3
3 4
4 5
5 6

输出 #3

122

输入输出样例 #4

输入 #4

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

输出 #4

19080

说明/提示

限制条件

  • 2≤N≤30002 \leq N \leq 3000
  • 1≤ai,bi≤N1 \leq a_i, b_i \leq N
  • 输入的图是一棵树

样例解释 1

满足条件的 PP 有以下 44 种:

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

由 ChatGPT 4.1 翻译