5505: 二叉搜索树(tree)

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

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

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

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

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

6
1 2 3
7 0 4
9 6 0
5 5 0
4 0 0
8 0 0

4