CF797D.Broken BST

Let T be arbitrary binary tree — tree, every vertex of which has no more than two children. Given tree is rooted, so there exists only one vertex which doesn't have a parent — it's the root of a tree. Every vertex has an integer number written on it. Following algorithm is run on every value from the tree T:

1. Set pointer to the root of a tree.
2. Return success if the value in the current vertex is equal to the number you are looking for
3. Go to the left child of the vertex if the value in the current vertex is greater than the number you are looking for
4. Go to the right child of the vertex if the value in the current vertex is less than the number you are looking for
5. Return fail if you try to go to the vertex that doesn't exist

Here is the pseudo-code of the described algorithm:

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);

The described algorithm works correctly if the tree is binary search tree (i.e. for each node the values of left subtree are less than the value in the node, the values of right subtree are greater than the value in the node). But it can return invalid result if tree is not a binary search tree.

Since the given tree is not necessarily a binary search tree, not all numbers can be found this way. Your task is to calculate, how many times the search will fail being running on every value from the tree.

If the tree has multiple vertices with the same values on them then you should run algorithm on every one of them separately.

设 $T$ 为任意一棵二叉树——即树中每个顶点至多有两个子节点。给定的树是有根树，因此仅存在一个没有父节点的顶点，该顶点即为树的根。每个顶点上写有一个整数。

对树 $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);  

当该树是一棵二叉搜索树（BST）（即对每个节点，其左子树中所有节点的值均小于该节点的值，其右子树中所有节点的值均大于该节点的值）时，上述算法能正确工作；但若该树不是二叉搜索树，则算法可能返回错误结果。

由于给定的树不一定是二叉搜索树，因此并非树中所有数值均能通过该方式被成功查找到。你的任务是：计算当对树中每一个值（注意：若树中存在多个顶点具有相同数值，则需对每个这样的顶点分别独立执行该算法）运行该搜索算法时，总共会失败多少次。

First line contains integer number n (1 ≤ n ≤ 105) — number of vertices in the tree.

Each of the next n lines contains 3 numbers v, l, r (0 ≤ v ≤ 109) — value on current vertex, index of the left child of the vertex and index of the right child of the vertex, respectively. If some child doesn't exist then number  - 1 is set instead. Note that different vertices of the tree may contain the same values.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——树中顶点的数量。

接下来的 $n$ 行，每行包含三个数 $v$、$l$、$r$（$0 \leq v \leq 10^9$）——分别表示当前顶点的值、该顶点左子节点的索引、该顶点右子节点的索引。若某个子节点不存在，则对应位置用 $-1$ 表示。注意：树中不同的顶点可能具有相同的值。

Print number of times when search algorithm will fail.

输出搜索算法失败的次数。

In the example the root of the tree in vertex 2. Search of numbers 5 and 15 will return fail because on the first step algorithm will choose the subtree which doesn't contain numbers you are looking for.

在示例中，树的根节点为顶点 2。查找数字 5 和 15 将返回失败，因为在第一步中，算法会选择不包含你所查找数字的子树。