← 返回题目列表

Codeforces · 797/D

D. 损坏的 BST

中文机器翻译题面 查看原题

设 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 的搜索将返回失败,因为第一步算法将选择不包含您要查找的数字的子树。