P1008商路照影（trade）

【题目背景】

在 Gioush 大队的营地深处，有一棵被称为商树的古树。

商树记录着营地内各处商会的报价与商路的走向。为了让 Gioush 大队的贸易维持应有的秩序，Ehundategh 决定重新核验商树上所有可能出现的交易。

【题目描述】

商树上共有 $n$ 处商会据点，编号为 $1\sim n$。其中 $1$ 号据点位于商树的最上方，是所有商路的起点。对于第 $i$ 处据点，它给出的商价为 $w_i$。

每一处商会最多会向下分出两条商路：一条通向左支商会，一条通向右支商会。对于第 $i$ 处商会，它的左支商会记为 $l_i$，右支商会记为 $r_i$。如果某一侧并没有继续通向其他商会的商路，则对应的编号记为 $0$。

在 Ehundategh 看来，一处商会并不只管理自己所在的位置。若从某处商会 $x$ 的左支商路出发，沿着商树向下能够到达若干商会，那么这些商会都属于 $x$ 的左支商队范围；同理，从 $x$ 的右支商路向下能够到达的所有商会，都属于 $x$ 的右支商队范围。

现在，一次被核验的贸易会从一处左支商会 $u$ 流向一处右支商会 $v$。如果对于某处商会 $x$，$u$ 属于 $x$ 的左支商队范围，$v$ 属于 $x$ 的右支商队范围，那么这次贸易在经过 $x$ 时完成中转。也就是说，$x$ 是这次贸易从左支走向右支时必须经过的中转商会。

但是，并非所有经过中转的贸易都会被记录。Gioush 大队认为，合理的贸易应当体现出价格逐步抬升的过程：左支商会给出的商价应当低于中转商会，而右支商会给出的商价应当高于中转商会。于是，若一组商会 $u,x,v$ 满足

那么从 $u$ 流向 $v$ 的这次贸易就会被记入账册。

现在，Ehundategh 想知道，在整棵商树中，一共存在多少个有序点对 $(u,v)$，使得可以找到某一处中转商会 $x$，令 $u$ 属于 $x$ 的左支商队范围，$v$ 属于 $x$ 的右支商队范围，并且这次贸易能够被记入账册。

【输入格式】

从文件 $\textbf{\textit{trade.in}}$ 中读入数据。

第一行一个正整数 $n$，表示商树中的节点数量。

第二行 $n$ 个整数，第 $i$ 个整数 $w_i$ 表示第 $i$ 个节点的商价。

接下来 $n$ 行，每行两个整数 $l_i,r_i$，分别表示第 $i$ 个节点的左儿子与右儿子。若对应儿子不存在，则为 $0$。

保证输入形成一棵以 $1$ 为根的二叉树。

【输出格式】

输出到文件 $\textbf{\textit{trade.out}}$ 中。

输出一行一个整数，表示可以被记录的有序点对数量。

【样例 1 输入】

1724 2 6 1 5 3 832 344 556 760 070 080 090 0

【样例 1 输出】

16

【说明/提示】

【样例 1 解释】

以 $1$ 号节点作为中转商会时，其左儿子子树中的节点为 $\{2,4,5\}$，右儿子子树中的节点为 $\{3,6,7\}$。

其中满足 $w_u<w_1<w_v$ 的有序点对为 $(2,3),(2,7),(4,3),(4,7)$，共 $4$ 对。

此外，以 $2$ 号节点作为中转商会时，$(4,5)$ 可以被记录；以 $3$ 号节点作为中转商会时，$(6,7)$ 可以被记录。因此答案为 $6$。

【样例 2】

见选手目录下的 $\textbf{\textit{trade/trade2.in}}$ 和 $\textbf{\textit{trade/trade2.ans}}$。

该组样例符合测试点 $9\sim 12$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{trade/trade3.in}}$ 和 $\textbf{\textit{trade/trade3.ans}}$。

该组样例符合测试点 $1\sim 8$ 的数据范围，且不存在同时拥有左支商队范围和右支商队范围的中转商会。

【样例 4】

见选手目录下的 $\textbf{\textit{trade/trade4.in}}$ 和 $\textbf{\textit{trade/trade4.ans}}$。

该组样例符合测试点 $9\sim 12$ 的数据范围，其中 $n=127$。

【数据范围】

特殊性质：对于任意节点 $u$，若 $l_u\neq0$，则有 $l_u=2u$；若 $r_u\neq0$，则有 $r_u=2u+1$。

对于 $100\%$ 的数据，保证：$1\leq n\leq 2\times 10^5$，$1\leq w_i\leq 10^9$。