后序树
题号：NC296391
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给定一棵由 n 个节点构成的以 1 为根节点的有根二叉树，每个节点都有一个权值 {\rm val}_i。你需要计算满足以下条件的联通块的数量：
\hspace{23pt}\bullet\,由联通块内每个节点的权值按照后序遍历编号的顺序组成的序列是非严格递增的。更具体地，记后序遍历中节点的编号为 b_1,b_2,\dots,b_k，则有 {\rm val}_{b_1} \leq {\rm val}_{b_2} \leq \dots \leq {\rm val}_{b_k}。
\hspace{15pt}由于答案可能很大，请将答案对 998\,244\,353 取模后输出。

【名词解释】
\hspace{15pt}对于树上的任意一个点集 \Bbb S，如果点集中的任意两点 u,v 满足“u 到 v 的简单路径上的所有点都在点集中”，则称 \Bbb S 是一个连通块。特别地，单独的点也构成一个连通块。

输入描述:

\hspace{15pt}第一行输入一个整数 n \left(1\leq n \leq 5 \times 10^5\right)，表示二叉树的节点数量。 
\hspace{15pt}第二行输入 n 个整数 {\rm val}_1, {\rm val}_2, \dots, {\rm val}_n \left(1\leq {\rm val}_i \leq 10^9 \right)，表示每个节点的权值。 
\hspace{15pt}此后 n 行，第 i 行输入两个整数 l_i 和 r_i \left(0\leq l_i,r_i \leq n\right)，表示节点 i 的左儿子和右儿子。若左/右儿子不存在，则对应值为 0。

输出描述:

\hspace{15pt}输出一个整数，表示满足条件的联通块的数量，对 998\,244\,353 取模后输出。
示例1

输入

复制 
5
3 1 2 1 2
2 3
0 4
0 5
0 0
0 0

输出

复制 
15

说明

\hspace{15pt}这个样例的树结构如下图所示：