CF797D Broken BST

给定一棵任意的二叉树——也就是说，树上的每个节点最多只有两个子节点。题目中给出的这棵树是有根树，因此存在且仅存在一个没有父节点的顶点——即为该树的根节点。每个节点上都写有一个整数。对于树 $T$ 中的每一个值，将按照如下算法运行一次： 1. 将指针指向树的根节点。 2. 如果当前节点上的值等于你要查找的数字，则查找成功，返回成功。 3. 如果当前节点上的值大于你要查找的数字，则转到当前节点的左子节点。 4. 如果当前节点上的值小于你要查找的数字，则转到当前节点的右子节点。 5. 如果尝试转到一个不存在的子节点，则查找失败，返回失败。 上述算法的伪代码如下： ``` bool find(TreeNode t, int x) { if (t == null) return false; if (t.value == x) return true; if (x < t.value) return find(t.left, x); else return find(t.right, x); } find(root, x); ``` 上述算法在树为二叉搜索树时能够正确工作（即每个节点的左子树中的值都小于该节点的值，右子树中的值都大于该节点的值）。但如果树不是二叉搜索树，则本算法可能给出错误的结果。 由于给定的树不一定是二叉搜索树，因此并非所有的数字都能用这种方式被查找到。你的任务是统计，对于树中每一个值分别运行一次查找算法，有多少次查找会失败。 如果树中有多个节点上写有相同的数字，那么对于每一个这样的节点都需要分别运行一次算法。

第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$），表示树中节点的数量。 接下来的 $n$ 行中，每行包含三个数字 $v,l,r$（$0 \leq v \leq 10^{9}$），表示当前节点上的值，其左子节点的编号和右子节点的编号。如果某个子节点不存在，则用 $-1$ 表示。注意，树中的不同节点可能拥有相同的值。

输出查找算法会失败的次数。

在样例中，树的根是编号为 $2$ 的节点。查找数字 $5$ 和 $15$ 时会失败，因为一开始算法就会选择到一个并不包含目标数字的子树。 由 ChatGPT 5 翻译