AT_arc183_e.[ARC183E] Ascendant Descendant

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一棵包含编号为 $1$ 到 $N$ 的 $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$ 是 good 的，当且仅当对每个 $i$ ，顶点 $A_i$ 是顶点 $B_i$ 的祖先，或者 $A_i = B_i$ 。

初始时，序列 $A$ 是 good 的。

我们考虑对序列 $A$ 进行以下操作：

选择一个整数 $i$ ( $1 \leq i \leq M-1$ )，交换 $A_i$ 和 $A_{i+1}$ 的值。操作后，序列 $A$ 仍必须是 good 的。

请计算，经过 $0$ 次或多次操作后，可能得到的不同序列的个数，并输出该结果对 $998244353$ 取模的值。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

输出可能得到的不同序列的个数，对 $998244353$ 取模。

输入输出样例

输入#1
```
3 3
1 2
1 2 1
1 2 3
```
输出#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

输入#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

说明/提示

$2 \leq N \leq 250000$
$2 \leq M \leq 250000$
$1 \leq P_i < i$
$1 \leq A_i \leq B_i \leq N$
对于每个 $i$ ，顶点 $A_i$ 是顶点 $B_i$ 的祖先，或者 $A_i = B_i$

样例解释

考虑选择 $i = 1$ 进行操作，操作后序列 $A=(2,1,1)$ 不是 good 的，因此该操作不可行。

再考虑选择 $i = 2$ 进行操作，操作后序列 $A=(1,1,2)$ 是 good 的，因此该操作可行。
可能得到的不同序列有 $A=(1,2,1)$ 和 $A=(1,1,2)$ ，因此答案是 $2$ 。

Translate by 宋怡芃

输入解题思路，AI测评打分。不知道怎么写?

首页