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:  Set pointer to the root of a tree.  Return success if the value in the current vertex is equal to the number you are looking for  Go to the left child of the vertex if the value in the current vertex is greater than the number you are looking for  Go to the right child of the vertex if the value in the current vertex is less than the number you are looking for  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.


-----Input-----

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

Each of the next n lines contains 3 numbers v, l, r (0 ≤ v ≤ 10^9) — 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.


-----Output-----

Print number of times when search algorithm will fail.


-----Examples-----
Input
3
15 -1 -1
10 1 3
5 -1 -1

Output
2

Input
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

Output
1



-----Note-----

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.

Difficulty: HARD
Tags: Data structures

Graph traversal
Skill types: Data structures

Starter code:

Solutions:
n = int(input().strip())
vlrs = [tuple(map(int, input().strip().split())) for _ in range(n)]
vlrs = [(v, l - (0 if l < 0 else 1), r - (0 if r < 0 else 1)) for (v, l, r) in vlrs]
isroot = [True for _ in range(n)]
for (v, l, r) in vlrs:
	if l != -1:
		isroot[l] = False
	if r != -1:
		isroot[r] = False
root = isroot.index(True)
vs = [v for (v, l, r) in vlrs]
vmin = min(vs)
vmax = max(vs)
found = set()

def DFS(U, vl, vr):
	while vlrs[U].count(-1) == 1:
		(v, L, R) = vlrs[U]
		if vl <= v <= vr:
			found.add(v)
		if L != -1:
			(U, vl, vr) = (L, vl, min(v, vr))
		else:
			(U, vl, vr) = (R, max(v, vl), vr)
	(v, L, R) = vlrs[U]
	if vl <= v <= vr:
		found.add(v)
	if L != -1 and R != -1:
		DFS(L, vl, min(v, vr))
		DFS(R, max(v, vl), vr)
DFS(root, vmin, vmax)
res = sum((1 for v in vs if v not in found))
print(res)


import sys
from collections import Counter
n = int(sys.stdin.buffer.readline().decode('utf-8'))
parent = [-1] * n
value = [0] * n
(left, right) = ([-1] * n, [-1] * n)
for (i, (v, l, r)) in enumerate((map(int, line.decode('utf-8').split()) for line in sys.stdin.buffer)):
	value[i] = v
	if l != -1:
		left[i] = l - 1
		parent[l - 1] = i
	if r != -1:
		right[i] = r - 1
		parent[r - 1] = i
root = parent.index(-1)
stack = [(root, -1, 10 ** 9 + 10)]
cnt_v = Counter()
cnt_ok = Counter()
while stack:
	(i, lb, ub) = stack.pop()
	cnt_v[value[i]] += 1
	if lb < value[i] < ub:
		cnt_ok[value[i]] = 1
	if left[i] != -1:
		stack.append((left[i], lb, min(ub, value[i])))
	if right[i] != -1:
		stack.append((right[i], max(lb, value[i]), ub))
ans = 0
for (k, v) in cnt_v.items():
	if cnt_ok[k] == 0:
		ans += v
print(ans)


from collections import deque
nodes = []
parents = []
values = []
broken = []
upperBound = []
lowerBound = []
n = int(input())
for _ in range(n):
	(v, l, r) = map(int, input().split())
	nodes.append((v, l - 1, r - 1))
	parents.append(-1)
	values.append(v)
	broken.append(False)
	upperBound.append(10 ** 9)
	lowerBound.append(-10 ** 9)
for (i, (v, l, r)) in enumerate(nodes):
	if l > -1:
		parents[l] = i
	if r > -1:
		parents[r] = i
root = -1
for i in range(n):
	if parents[i] == -1:
		root = i
proc = deque([root])
while len(proc) > 0:
	node = proc.popleft()
	(v, l, r) = nodes[node]
	if l > -1:
		proc.append(l)
		upperBound[l] = min(upperBound[node], v)
		lowerBound[l] = lowerBound[node]
		if not lowerBound[l] <= nodes[l][0] <= upperBound[l]:
			broken[l] = True
	if r > -1:
		proc.append(r)
		upperBound[r] = upperBound[node]
		lowerBound[r] = max(lowerBound[node], v)
		if not lowerBound[r] <= nodes[r][0] <= upperBound[r]:
			broken[r] = True
s = set([])
for (v, b) in zip(values, broken):
	if not b:
		s.add(v)
ans = 0
for v in values:
	if v not in s:
		ans += 1
print(ans)