1004 - 树上连通块

给你一棵N个节点构成的有根二叉树,其中1为根,每个节点有权值为VAL,你需要计算满足如下条件的连通块的数量: 由联通块内每个节点的权值按照后续遍历的顺序组成的序号是非严格递增的,更具体的,记后续遍历中节点的编号为B1,B2,B3....BK,则有VALB1 < VALB2 < ...< VALBK 由于答案较大,请对998244353取模

输入

第一行一个整数N,表示节点数 (1<=N<=200000)

第二行,N个整数,表示每个节点的权值

接下来N行,第I行输入2个整数LI,RI,表示节点I的左儿子和右儿子,如左或右儿子不存在,则对应位置为0

输出

输出一个取模后的整数

样例

输入

5
3 1 2 1 2
2 3
0 4
0 5
0 0
0 0

输出

15
时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题