← 返回题目列表

AtCoder · arc183_e

E. 上升后代

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

分数: 900 点

问题陈述

有一棵有根的树 N 顶点编号自 1 to N。 根是顶点 1,以及顶点的父级 i (2 \leq i \leq N) 是顶点 P_i (P_i<i).

还有长度为整数的序列 M: A=(A_1,A_2,\cdots,A_M) 和 B=(B_1,B_2,\cdots,B_M),由之间的整数组成 1 和 N,包括在内。

A 据说是 好 当且仅当对于每个 i,顶点 A_i 是顶点的祖先 B_i or A_i=B_i。 最初, A 很好。

考虑以下操作 A.

  • 选择一个整数 i (1 \leq i \leq M-1)并交换值 A_i 和 A_{i+1}。 在这里, A 手术后必须保持良好状态。

求模数 998244353,执行此操作可能产生的序列 A 零次或多次。

约束

  • 2 \leq N \leq 250000
  • 2 \leq M \leq 250000
  • 1 \leq P_i <i
  • 1 \leq A_i \leq B_i \leq N
  • 顶点 对于所有整数, A_i 是顶点的祖先 B_i or A_i=B_i.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
P_2 P_3 \cdots P_N
A_1 A_2 \cdots A_M
B_1 B_2 \cdots B_M

输出

打印答案。


样本输入 1

3 3
1 2
1 2 1
1 2 3

示例输出 1

2

考虑选择 i=1.The A=(2,1,1) 操作后效果不好,所以本次操作无效。

考虑选择 i=2.The A=(1,1,2) 操作好后,所以本次操作有效。

执行零个或多个操作可能会产生两个序列 A: A=(1,2,1) 和 (1,1,2).


示例输入 2

4 3
1 1 1
2 3 4
2 3 4

示例输出 2

1

示例输入 3

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

示例输出 3

8

示例输入 4

30 27
1 2 1 1 5 1 7 1 5 10 1 12 12 13 15 16 12 18 19 18 21 21 23 13 18 18 27 27 13
1 18 1 5 11 12 1 1 1 12 1 12 1 15 1 1 21 1 12 10 2 8 3 1 1 30 12
14 27 30 5 11 17 1 18 24 27 29 27 19 15 28 5 21 21 29 11 2 8 3 4 10 30 22

示例输出 4

60