Pre-Order

题目描述

有一个以顶点 $1$ 为根的有 $N$ 个顶点的根树，顶点编号为 Vertex $1$, $2$, $\ldots$, $N$。 我们从根开始进行深度优先搜索，得到树的先序遍历：$P_1, P_2, \ldots, P_N$.
在搜索过程中，当当前顶点有多个孩子时，我们选择尚未被访问且编号最小的顶点。

什么是先序遍历？

我们从根开始重复以下过程以列出树的顶点。

如果当前顶点 $u$ 尚未被记录，则记录它。 然后，如果 $u$ 有尚未访问的顶点，则前往该顶点。 否则，如果 $u$ 是根则终止，否则回到 $u$ 的父节点。

在此记录顺序中的顶点列表就是树的先序遍历。

求与该先序遍历一致的根树的数量，对 $998244353$ 取模。
当存在一个非根顶点在两棵树中的父节点不同，则认为这两棵根树不同。

输入格式

输入从标准输入按以下格式给出： $N$ $P_1$ $P_2$ $\ldots$ $P_N$

输出格式

输出与该先序遍历一致的根树的数量，对 $998244353$ 取模。

4
1 2 4 3

3

8
1 2 3 5 6 7 8 4

202

提示

$2 \leq N \leq 500$ $1 \leq P_i\leq N$ $P_1=1$ 所有 $P_i$ 互不相同。 输入中的所有数值均为整数。与该先序遍历一致的根树有下面三棵，因此答案为 $3$。 注意下面的树不计入。这是因为，在顶点 $2$ 的孩子中，我们在访问顶点 $4$ 之前访问了顶点 $3$，导致先序遍历为 $1,2,3,4$。

标签: AtCoder|abc252G

来源

AtCoder|abc252G