二叉搜索树（tree）

【题目背景】

在本题中，二叉搜索树是一种二叉树的树形数据结构，其定义如下：

若二叉搜索树的左子树不为空，则其左子树上所有点的权值均小于等于其根节点的值。若二叉搜索树的右子树不为空，则其右子树上所有点的权值均大于等于其根节点的值。二叉搜索树的左右子树均为二叉搜索树。

【题目描述】

小明有一棵n个节点树，用1-n编号，其中根节点是1，第i个节点的权值为v_i，但是不满足二叉搜索树的要求，小明希望不改变树的形状，仅通过若干次交换（交换是指交换两个节点的权值），使得树变成二叉搜索树。求有多少个节点不用参与交换，即有多少个节点一开始就在正确的位置。

输入的第一行包含一个正整数 n，表示树的节点数量。

接下来n行，每行三个整数v_i 、l_i 、r_i分别表示节点的权值，节点的左儿子编号，右儿子编号，编号的值为0表示树没有，对应的子树。

输出仅一个数字，表示不需要参与交换的节点数量

【样例1解释】

初始树的状态如下：圈内表示节点编号，圈外数字表示节点对应的权值。

下图为正确的二叉搜索树，其中节点1和节点2的权值需要交换，节点3、4、5、6不需要交换。

【数据范围】

对于所有测试数据有：1≤v_i≤10^9,1≤n≤5×10^5。

特殊性质A: 对于所有的l_i 、r_i要么同时为0，要么同时不为0。

特殊性质B：对于任意的1≤i,j≤n,i≠j，都有v_i≠v_j。

云南编程挑战赛