改造二叉树

【问题描述】 在计算机科学中，二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子”。

二叉树常被用作二叉搜索树和二叉堆。

我们再讨论二叉搜索树。什么是二叉搜索树呢？二叉搜索树首先是一棵二叉树。设$key[p]$表示结点$p$上的数值，

对于其中的每个结点$p$，若其存在左孩子$lch$，则$key[p]>key[lch]$；若其存在右孩子$rch$，则$key[p]$$

注意，应该是所有左子树中的$key$小于当前$key$，所有右子树中的$key$大于当前$key$。

对于每个结点，无论如何改变其数值（整数），费用总等于$1$。

现在给定一棵二叉树，可以任意修改结点的数值。要求用最小的费用将其变成一棵二叉搜索树。

【输入】

输入文件bst.in包括两行，第一行是一个整数$n$，表示二叉树的结点数。

第二行包含$n$个整数，用空格分隔，第i个整数$ai$是第$i$个结点的原始数值。

此后$n-1$行每行两个整数，第$i$行描述编号为$i-1$的结点的父亲编号以及父子关系（0表示为左孩子，1表示为右孩子）。编号为1的结点一定是二叉树的根。

【输出】

输出文件bst.out包括一行，这一行只包含一个整数，也就是最小的费用值。输入数据保证这个值小于$2^{31}$。

【样例输入】

3

2 2 2

1 0

1 1

【样例输入】

2

【数据范围】 对于50%的数据，保证n<=100且0<=ai<=200；

对于100%的数据，保证n<=100000；

10个测试点