设 T 是任意二叉树,每个顶点的子节点不超过两个。给定的树是有根的,因此只存在一个没有父节点的顶点 - 它是树的根。每个顶点上都写有一个整数。以下算法对树 T 中的每个值运行:
1. 将指针设置为树的根。
2.如果当前顶点的值等于要查找的数字则返回成功
3.如果当前顶点中的值大于您要查找的数字,则转到顶点的左子节点
4.如果当前顶点中的值小于要查找的数字,则转到顶点的右子节点
5. 如果尝试去不存在的顶点则返回失败
这是所描述算法的伪代码:
如果树是二叉搜索树(即,对于每个节点,左子树的值小于该节点中的值,右子树的值大于该节点中的值),则所描述的算法可以正确工作。但如果树不是二叉搜索树,它可能会返回无效结果。
由于给定的树不一定是二叉搜索树,因此并非所有数字都可以通过这种方式找到。您的任务是计算对树中的每个值运行搜索失败的次数。
如果树有多个具有相同值的顶点,那么您应该分别对每个顶点运行算法。
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 树中的顶点数。
接下来的 n 行中的每一行包含 3 个数字 v、l、r (0 ≤ v ≤ 109) — 分别是当前顶点的值、顶点左子节点的索引和顶点右子节点的索引。如果某个子项不存在,则设置 number - 1。请注意,树的不同顶点可能包含相同的值。
输出
打印搜索算法失败的次数。
示例
输入 #1
3 15 -1 -1 10 1 3 5 -1 -1
输出 #1
2
输入 #2
8 6 2 3 3 4 5 12 6 7 1 -1 8 4 -1 -1 5 -1 -1 14 -1 -1 2 -1 -1
输出 #2
1
注意
在示例中,树的根位于顶点 2。数字 5 和 15 的搜索将返回失败,因为第一步算法将选择不包含您要查找的数字的子树。