A pair of nodes, $(a,b)$, is a similar pair if the following conditions are true:

node $a$ is the ancestor of node $b$
$abs(a-b)\leq k$

Given a tree where each node is labeled from $1$ to $n$, find the number of similar pairs in the tree.

For example, given the following tree:  

We have the following pairs of ancestors and dependents:  

Pair	abs(a-b)	Pair	abs(a-b)
1,2	1		3,4	1
1,3	2		3,5	2
1,4	3		3,6	3
1,5	4
1,6	5

If $k=3$ for example, we have $6$ pairs that are similar, where $abs(a-b)\leq k$.

Function Description

Complete the similarPair function in the editor below.  It should return an integer that represents the number of pairs meeting the criteria.

similarPair has the following parameter(s):  

n: an integer that represents the number of nodes  
k: an integer
edges: a two dimensional array where each element consists of two integers that represent connected node numbers  

Input Format

The first line contains two space-separated integers $n$ and $k$, the number of nodes and the similarity threshold. 

Each of the next $n-1$ lines contains two space-separated integers defining an edge connecting nodes $p[i]$ and $c[i]$, where node $p[i]$ is the parent to node $c[i]$.

Constraints

$1\leq n\leq10^5$  
$0\leq k\leq n$  
$1\leq p[i],c[i]\leq n$  

Output Format

Print a single integer denoting the number of similar pairs in the tree.

Sample Input
5 2
3 2
3 1
1 4
1 5

Sample Output
4

Explanation

The similar pairs are $(3,2)$, $(3,1)$, $(3,4)$, and $(3,5)$, so we print $4$ as our answer. 

Observe that $(1,4)$ and $(1,5)$ are not similar pairs because they do not satisfy $abs(a-b)\leq k$ for $k=2$.

Source: hackerrank | Difficulty: HARD
Tags: Complete search


Solutions:
(n, m) = list(map(int, input().strip().split(' ')))
graph = [[] for i in range(n)]
matrix = [i for i in range(n)]
for i in range(n - 1):
	(a, b) = list(map(int, input().strip().split(' ')))
	matrix[b - 1] = a - 1
	graph[a - 1].append(b - 1)
p = 0
while matrix[p] != p:
	p = matrix[p]
import bisect
total = 0
stack = [p]
path = []
while stack:
	n = stack.pop()
	if type(n) == tuple:
		path.pop(n[0])
		continue
	total += bisect.bisect_right(path, n + m) - bisect.bisect_left(path, n - m)
	if not graph[n]:
		continue
	i = bisect.bisect_left(path, n)
	path.insert(i, n)
	stack.append((i,))
	stack.extend(graph[n])
print(total)


(n, T) = [int(x) for x in input().split()]
children = {}
parent = {}
root = None
for i in range(0, n - 1):
	(p, c) = [int(x) for x in input().split()]
	if p not in children:
		children[p] = set()
	children[p].add(c)
	parent[c] = p
for p in children:
	if p not in parent:
		root = p

class Bit:

	def __init__(self, n):
		sz = 1
		while n >= sz:
			sz *= 2
		self.size = sz
		self.data = [0] * sz

	def sum(self, i):
		assert i > 0
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		assert i > 0
		while i < self.size:
			self.data[i] += x
			i += i & -i
t = Bit(n)
l = [root]
acum = 0
parents = set()
while l:
	x = l.pop()
	if x in children:
		l.append(x)
		l.extend(children[x])
		del children[x]
		t.add(x, 1)
		parents.add(x)
	else:
		if x in parents:
			parents.remove(x)
			t.add(x, -1)
		up = min(x + T, n)
		down = max(x - T - 1, 0)
		if down > 0:
			am = t.sum(up) - t.sum(down)
		else:
			am = t.sum(up)
		acum += am
print(acum)


from collections import abc
import bisect

class sortedlist(abc.MutableSequence):

	def __init__(self):
		self.l = []

	def __getitem__(self, key):
		return self.l[key]

	def __setitem__(self, k, v):
		return NotImplemented

	def __delitem__(self, k):
		self.l.__delitem__(k)

	def __contains__(self, v):
		return self.l[bisect.bisect_left(self.l, v)] == v

	def __len__(self):
		return self.l.__len__()

	def __iter__(self):
		return self.l.__iter__()

	def __reversed__(self):
		return NotImplemented

	def insert(self, k, v):
		return NotImplemented

	def append(self, v):
		self.l.insert(bisect.bisect_left(self.l, v), v)

	def reverse(self):
		return NotImplemented

	def extend(self, v):
		return NotImplemented

	def pop(self):
		return NotImplemented

	def remove(self, v):
		del self.l[bisect.bisect_left(self.l, v)]

	def __iadd__(self, v):
		return NotImplemented

	def __repr__(self):
		return self.l.__repr__()

	def __str__(self):
		return self.l.__str__()

class Node:

	def __init__(self, id):
		self.id = id
		self.parent = None
		self.children = set()

	def addChild(self, child):
		self.children.add(child)
		child.parent = self

	def root(self):
		p = self
		while p.parent:
			p = p.parent
		return p

	def traceroot(self):
		r = [self]
		while r[-1].parent:
			r.append(r[-1].parent)
		return r

	def __hash__(self):
		return hash(self.id)

	def __eq__(self, o):
		return self.id == o.id if type(o) is Node else self.id == o

	def __lt__(self, o):
		return self.id < o.id if type(o) is Node else self.id < o

	def __gt__(self, o):
		return self.id > o.id if type(o) is Node else self.id > o

	def __repr__(self):
		return '<{}:p:{}:{}>'.format(self.id, self.parent.id if self.parent else None, [x.id for x in self.children])
(n, t) = map(int, input().split())
tree = []
for i in range(n):
	tree.append(Node(i))
lam = lambda x: int(x) - 1
for _ in range(n - 1):
	(p, c) = map(lam, input().split())
	tree[p].addChild(tree[c])
l = sortedlist()
r = tree[0].root()
s = [r]
v = set([r])
l.append(r)
p = 0
while len(s):
	c = s[-1]
	ch = sorted(c.children - v)
	if len(ch):
		s.append(ch[0])
		v.add(ch[0])
		l.append(ch[0])
	else:
		l.remove(c)
		s.pop()
		p += bisect.bisect_right(l, c.id + t) - bisect.bisect_left(l, c.id - t)
print(p)


class BITreeSet(object):

	def __init__(self, arr, max_num=10 ** 5):
		self.max_num = max_num
		self.array = [0 for _ in range(max_num + 1)]
		for integer in arr:
			if 0 < integer < self.max_num + 1:
				self.incr_value(integer, 1)
		return

	def get_sum(self, index):
		if 0 <= index <= self.max_num:
			the_sum = 0
			while index > 0:
				the_sum += self.array[index]
				index = index - (index & -index)
			return the_sum
		else:
			print('Index Error')
			return

	def incr_value(self, n, incr):
		if 0 < n <= self.max_num:
			while n < len(self.array):
				self.array[n] += incr
				n = n + (n & -n)
		return

	def get(self, n):
		if 0 < n <= self.max_num:
			return self.get_sum(n) - self.get_sum(n - 1)
		else:
			print('Index Error')
		return

	def set_value(self, n, value):
		if 0 < n <= self.max_num:
			difference = value - self.get(n)
			self.incr_value(n, difference)
		else:
			print('Index Error')
		return

	def count_range(self, n0, n1):
		if n1 >= n0:
			if n1 > self.max_num:
				n1 = self.max_num
			if n0 < 1:
				n0 = 1
			return self.get_sum(n1) - self.get_sum(n0 - 1)
		else:
			print('Index Error')
			return

	def add(self, n):
		self.set_value(n, 1)
		return

	def remove(self, n):
		self.set_value(n, 0)
		return

	def contains(self, n):
		return self.count_range(n, n) == 1

class Int_Node(object):

	def __init__(self, n):
		self.num = n
		self.kids = set()

	def children(self):
		return self.kids

	def number(self):
		return self.num

	def add_child(self, node):
		self.kids.add(node)

	def __str__(self):
		return str(self.num)

class Stack(object):

	def __init__(self):
		self.theArray = []
		self.size = 0

	def push(self, n):
		self.theArray.append(n)
		self.size += 1

	def peek(self):
		return self.theArray[self.size - 1]

	def pop(self):
		self.size -= 1
		return self.theArray.pop()

	def __len__(self):
		return self.size

	def __nonzero__(self):
		if self.size == 0:
			return 0
		return 1

	def __str__(self):
		stringy = '['
		for item in self.theArray:
			stringy += str(item)
			stringy += ', '
		stringy += ']'
		return stringy

def find_num_similar(n, t, ancestor):
	return ancestor.count_range(n - t, n + t)
(n, t) = input().strip().split(' ')
(n, t) = (int(n), int(t))
node_finder = n * (n + 1) // 2
num_to_nodes = {}
for _ in range(n - 1):
	(parent, child) = input().strip().split(' ')
	(parent, child) = (int(parent), int(child))
	node_finder -= child
	if child not in num_to_nodes:
		child_node = Int_Node(child)
		num_to_nodes[child] = child_node
	else:
		child_node = num_to_nodes[child]
	if parent not in num_to_nodes:
		parent_node = Int_Node(parent)
		num_to_nodes[parent] = parent_node
	else:
		parent_node = num_to_nodes[parent]
	parent_node.add_child(child_node)
root_num = node_finder
root = num_to_nodes[root_num]
anc_stack = Stack()
children_stack = Stack()
ancestor_set = BITreeSet([], n)
anc_stack.push(root)
for child in root.children():
	children_stack.push(child)
ancestor_set.add(root.number())
num_similar = 0
while children_stack:
	new_child = children_stack.pop()
	for grandchild in new_child.children():
		children_stack.push(grandchild)
	while new_child not in anc_stack.peek().children():
		young_anc = anc_stack.pop()
		ancestor_set.remove(young_anc.number())
		num_similar += find_num_similar(young_anc.number(), t, ancestor_set)
	anc_stack.push(new_child)
	ancestor_set.add(new_child.number())
while anc_stack:
	young_anc = anc_stack.pop()
	ancestor_set.remove(young_anc.number())
	num_similar += find_num_similar(young_anc.number(), t, ancestor_set)
print(num_similar)


from collections import OrderedDict
import sys
import json
sys.setrecursionlimit(1500)
values = list(sys.stdin)
(N, T) = [int(val) for val in values[0].split()]
graph = [None] * (N + 1)
tree = [0] * ((N + 1) * 4)
degs = [0] * (N + 1)

def query(index, left, right, begin, end):
	stack = [(index, left, right, begin, end)]
	append = stack.append
	vals = []
	add_val = vals.append
	while stack:
		(index, left, right, begin, end) = stack.pop()
		if right < begin or left > end:
			add_val(0)
			continue
		if left <= begin and right >= end:
			add_val(tree[index])
			continue
		mid = int(begin + (end - begin) / 2)
		append((index * 2, left, right, begin, mid))
		append((index * 2 + 1, left, right, mid + 1, end))
		continue
	return sum(vals)

def update(index, node, val, begin, end):
	stack = []
	append = stack.append
	append((index, node, val, begin, end))
	while stack:
		(index, node, val, begin, end) = stack.pop()
		if node < begin or node > end:
			continue
		if begin <= node and node <= end:
			tree[index] += val
		if begin == node and end == node:
			continue
		mid = int(begin + (end - begin) / 2)
		append((index * 2, node, val, begin, mid))
		append((index * 2 + 1, node, val, mid + 1, end))

def find_pairs(root):
	stack = [(root, (1, root, -1, 1, N))]
	append = stack.append
	sims = []
	add_sim = sims.append
	while stack:
		(root, next) = stack.pop()
		if root == None:
			update(*next)
			continue
		l = max(1, root - T)
		r = min(N, root + T)
		sim = query(1, l, r, 1, N)
		add_sim(sim)
		update(1, root, 1, 1, N)
		next_roots = graph[root]
		append((None, (1, root, -1, 1, N)))
		if next_roots:
			for deg in graph[root]:
				append((deg, None))
	return sum(sims)

def add_node(si, ei):
	si = int(si)
	ei = int(ei)
	try:
		graph[si].append(ei)
	except AttributeError:
		graph[si] = [ei]
	degs[ei] += 1
[add_node(*line.split()) for line in values[1:]]
root = -1
for (i, deg) in enumerate(degs[1:]):
	if deg == 0:
		root = i + 1
		break
print(find_pairs(root))


class Bit:

	def __init__(self, n):
		sz = 1
		while n >= sz:
			sz *= 2
		self.size = sz
		self.data = [0] * sz

	def sum(self, i):
		if i == 0:
			return 0
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		assert i > 0
		while i < self.size:
			self.data[i] += x
			i += i & -i

def dfs(Tree, root, thr):
	res = 0
	bit = Bit(len(Tree) + 1)
	counts = [0] * len(Tree)
	stack = [root]
	while stack:
		v = stack[-1]
		childs = [] if counts[v] else Tree[v]
		if not counts[v]:
			bit.add(v, 1)
		counts[v] = 1
		stack.extend(childs)
		if not childs:
			stack.pop()
			counts[v] = 0
			bit.add(v, -1)
			minindex = max(1, v - thr)
			maxindex = min(len(Tree), v + thr)
			res += bit.sum(maxindex) - bit.sum(minindex - 1)
	return res
(n, T) = map(int, input().split())
Tree = [[] for _ in range(n + 1)]
root = -1
for _ in range(n - 1):
	(v1, v2) = map(int, input().split())
	Tree[v1].append(v2)
	if root == -1:
		root = v1
print(dfs(Tree, root, T))


(n, T) = [int(x) for x in input().split()]
edge = [None] + [[] for _ in range(n)]
in_count = [None] + [0] * n
for _ in range(n - 1):
	(i, j) = [int(x) for x in input().split()]
	edge[i].append(j)
	in_count[j] += 1
root = in_count.index(0)
BIT = [0] * (n + 1)

def update(idx, v):
	while idx <= n:
		BIT[idx] += v
		idx += idx & -idx

def get(idx):
	r = 0
	while idx > 0:
		r += BIT[idx]
		idx -= idx & -idx
	return r
ans = 0
stack = [root]
while stack:
	p = stack[-1]
	if p > 0:
		upper_bound = min(p + T, n)
		lower_bound = max(p - T, 1)
		ans += get(upper_bound) - get(lower_bound - 1)
		stack[-1] *= -1
		update(p, 1)
		for child in edge[p]:
			stack.append(child)
	else:
		update(-p, -1)
		stack.pop()
print(ans)


def read_input():
	(num_nodes, T) = map(int, str.split(input()))
	tree = [{'child': []} for i in range(num_nodes)]
	for i in range(num_nodes - 1):
		(parent, child) = map(int, str.split(input()))
		parent -= 1
		child -= 1
		if i == 0:
			root = parent
		tree[parent]['child'].append(child)
	return (num_nodes, T, tree, root)

def bit_set(bit, index, value):
	index += 1
	while index < len(bit):
		bit[index] += value
		index += index & -index

def bit_get(bit, index):
	index += 1
	value = 0
	while index > 0:
		value += bit[index]
		index -= index & -index
	return value

def bit_add(bit, index):
	bit_set(bit, index, +1)

def bit_remove(bit, index):
	bit_set(bit, index, -1)
(n, T, tree, root) = read_input()
bit = [0] * (n + 1)
nodelist = [{'index': root, 'removeBit': False}]
similar_pairs = 0
while True:
	if len(nodelist) == 0:
		break
	node = nodelist.pop()
	if node['removeBit']:
		similar_pairs = similar_pairs
		bit_remove(bit, node['index'])
	else:
		ans_before = bit_get(bit, max(0, node['index'] - T - 1))
		if node['index'] - T - 1 < 0:
			ans_before = 0
		ans_after = bit_get(bit, min(n - 1, node['index'] + T))
		similar_pairs += ans_after - ans_before
		if len(tree[node['index']]['child']):
			bit_add(bit, node['index'])
			nodelist.append({'index': node['index'], 'removeBit': True})
			for i in range(len(tree[node['index']]['child'])):
				nodelist.append({'index': tree[node['index']]['child'][i], 'removeBit': False})
print(similar_pairs)


from array import array
from collections import defaultdict, deque
from functools import partial
import sys
import resource
sys.setrecursionlimit(300000)
resource.setrlimit(resource.RLIMIT_STACK, (resource.RLIM_INFINITY, resource.RLIM_INFINITY))

class Bit:

	def __init__(self, n):
		self._n = n
		self._bit = array('i', (0 for _ in range(n + 1)))

	def get(self, i):
		res = 0
		while i:
			res += self._bit[i]
			i -= i & -i
		return res

	def set(self, i):
		while i <= self._n:
			self._bit[i] += 1
			i += i & -i

	def unset(self, i):
		while i <= self._n:
			self._bit[i] -= 1
			i += i & -i
readpair = lambda : map(int, sys.stdin.readline().split(' '))
tree = defaultdict(list)
deq = deque()

class checker:

	def __init__(self, n, t):
		self._n = n
		self._bit = Bit(n)
		self._cnt = 0
		self._t = t

	def doit(self, i):
		lower = max([i - self._t - 1, 0])
		upper = min([self._t + i, self._n])
		self._bit.get(upper)
		try:
			self._bit.get(lower)
		except:
			print(lower)
		self._cnt += self._bit.get(upper) - self._bit.get(lower)
		self._bit.set(i)
		list((self.doit(child) for child in tree[i]))
		self._bit.unset(i)
		return self._cnt

def main():
	(n, t) = readpair()
	rootset = {x for x in range(1, n + 1)}
	for i in range(1, n):
		(a, s) = readpair()
		rootset.remove(s)
		tree[a].append(s)
	root = rootset.pop()
	check = checker(n, t)
	print(check.doit(root))
main()


class BinaryNode:

	def __init__(self, value):
		self.value = value
		self.parent = None
		self.right = None
		self.left = None
		self.tree_size = 0
		self.height = 0

	def update(self):
		my_node = self
		while True:
			if abs(my_node.height_left - my_node.height_right) > 1:
				my_node.rotate()
			my_node.update_single()
			if my_node.parent is None:
				break
			my_node = my_node.parent
		return my_node

	def update_single(self):
		self.tree_size = self.tree_size_left + self.tree_size_right + 1
		self.height = max(self.height_right, self.height_left) + 1

	def rotate(self):
		while abs(self.height_left - self.height_right) > 1:
			if self.height_left > 1 + self.height_right:
				if self.left.height_left >= self.left.height_right:
					self.rotate_right()
				else:
					self.left.rotate_left()
					self.rotate_right()
			elif self.height_right > 1 + self.height_left:
				if self.right.height_right >= self.right.height_left:
					self.rotate_left()
				else:
					self.right.rotate_right()
					self.rotate_left()

	def rotate_right(self):
		parent = self.parent
		y = self
		x = self.left
		b = x.right
		if parent is not None:
			if y is parent.right:
				parent.right = x
			elif y is parent.left:
				parent.left = x
		y.left = b
		if b is not None:
			b.parent = y
		x.parent = parent
		x.right = y
		y.parent = x
		x.update_single()
		y.update_single()

	def rotate_left(self):
		parent = self.parent
		x = self
		y = self.right
		b = y.left
		if parent is not None:
			if x is parent.right:
				parent.right = y
			elif x is parent.left:
				parent.left = y
		x.right = b
		if b is not None:
			b.parent = x
		y.parent = parent
		x.parent = y
		y.left = x
		x.update_single()
		y.update_single()

	def walk(self, result=None):
		if result is None:
			result = []
		if self.left is not None:
			self.left.walk(result)
		result.append(self.value)
		if self.right is not None:
			self.right.walk(result)
		return result

	def get_max_node(self):
		my_node = self
		while my_node.right is not None:
			my_node = my_node.right
		return my_node

	def delete(self, value):
		delete_node = self.find_node(value, True)
		update_node = None
		if delete_node is None:
			return self
		if delete_node.left is None and delete_node.right is None:
			if delete_node.parent is None:
				return None
			if delete_node is delete_node.parent.right:
				delete_node.parent.right = None
			else:
				delete_node.parent.left = None
			return delete_node.parent.update()
		if delete_node.left is None:
			promoted_node = delete_node.right
		elif delete_node.right is None:
			promoted_node = delete_node.left
		else:
			promoted_node = delete_node.left.get_max_node()
			if promoted_node.parent is not delete_node:
				if promoted_node.left is not None:
					promoted_node.left.parent = promoted_node.parent
				update_node = promoted_node.parent
				promoted_node.parent.right = promoted_node.left
				promoted_node.left = None
		delete_node.swap_nodes(promoted_node)
		if update_node is None:
			return promoted_node.update()
		else:
			return update_node.update()

	def swap_nodes(self, target):
		if self.parent is not None:
			if self is self.parent.right:
				self.parent.right = target
			else:
				self.parent.left = target
		target.parent = self.parent
		if self.right is not None and self.right is not target:
			self.right.parent = target
			target.right = self.right
		if self.left is not None and self.left is not target:
			self.left.parent = target
			target.left = self.left

	def find_node(self, search_val, exact=True):
		this_node = self
		while True:
			if search_val < this_node.value:
				if this_node.left is None:
					return None if exact else this_node
				this_node = this_node.left
			elif search_val > this_node.value:
				if this_node.right is None:
					return None if exact else this_node
				this_node = this_node.right
			else:
				return this_node

	@property
	def tree_size_left(self):
		return 0 if self.left is None else self.left.tree_size

	@property
	def tree_size_right(self):
		return 0 if self.right is None else self.right.tree_size

	@property
	def height_left(self):
		return -1 if self.left is None else self.left.height

	@property
	def height_right(self):
		return -1 if self.right is None else self.right.height

	def add(self, my_node):
		this_node = self
		while True:
			if my_node < this_node:
				if this_node.left is None:
					this_node.left = my_node
					my_node.parent = this_node
					return my_node.update()
				else:
					this_node = this_node.left
			elif this_node.right is None:
				this_node.right = my_node
				my_node.parent = this_node
				return my_node.update()
			else:
				this_node = this_node.right

	def get_rank(self, search_val, include_exact=False):
		this_node = self
		rank = 0
		while this_node is not None:
			if search_val < this_node.value:
				this_node = this_node.left
			elif search_val > this_node.value:
				rank += 1 + this_node.tree_size_left
				this_node = this_node.right
			else:
				rank += this_node.tree_size_left
				if include_exact:
					rank += 1
				break
		return rank

	def __lt__(self, other):
		return self.value < other.value

	def __gt__(self, other):
		return self.value > other.value

	def __str__(self):
		return str(self.value)

class RangeFinder:

	def __init__(self):
		self.root_node = None

	def add(self, node_id):
		my_node = BinaryNode(node_id)
		if self.root_node is None:
			self.root_node = my_node
			self.root_node.update()
		else:
			self.root_node = self.root_node.add(my_node)

	def remove(self, node_id):
		if self.root_node is None:
			return
		else:
			self.root_node = self.root_node.delete(node_id)

	def range_count(self, min_val, max_val):
		if self.root_node is None:
			count = 0
		else:
			min_rank = self.root_node.get_rank(min_val, False)
			max_rank = self.root_node.get_rank(max_val, True)
			count = max_rank - min_rank
		return count

def read_input():
	(nodes, T) = get_int_list(input())
	edge_list = []
	for i_edges in range(nodes - 1):
		edge_list.append(get_int_list(input()))
	return (nodes, T, edge_list)

class Tree:

	def __init__(self):
		(nodes, self.T, edge_list) = read_input()
		self.root_id = edge_list[0][0]
		self.pointers = {i: TreeNode(i) for i in range(1, 1 + nodes)}
		self.root = self.pointers[self.root_id]
		for (parent_id, child_id) in edge_list:
			parent = self.pointers[parent_id]
			child = self.pointers[child_id]
			parent.children.append(child)
			child.parent = parent

	def calculate(self):
		return self.dfs_for_silly_non_recursive_python()

	def dfs_for_silly_non_recursive_python(self):
		process_list = [self.root]
		visited_set = set()
		range_finder = RangeFinder()
		pairs = 0
		while len(process_list) > 0:
			my_node = process_list[len(process_list) - 1]
			if my_node.paused:
				range_finder.remove(my_node.id)
				process_list.pop()
			else:
				visited_set.add(my_node.id)
				pairs += range_finder.range_count(my_node.id - self.T, my_node.id + self.T)
				for child in my_node.children:
					if child.id not in visited_set:
						process_list.append(child)
						my_node.paused = True
				if my_node.paused:
					range_finder.add(my_node.id)
				else:
					process_list.pop()
		return pairs

class TreeNode:

	def __init__(self, node_id):
		self.id = node_id
		self.parent = None
		self.children = []
		self.paused = False

	def __str__(self):
		return '%s: %s' % (self.id, len(self.children))

def main():
	my_obj = Tree()
	print(my_obj.calculate())

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()


class Fenwick(list):

	def __init__(self, n):
		self.n = n
		super().__init__([0] * n)

	def add(self, i, val):
		i = i + 1
		while i <= self.n:
			self[i - 1] += val
			i += i & -i

	def sum(self, i):
		val = 0
		while i > 0:
			val += self[i - 1]
			i -= i & -i
		return val

	def get(self, i):
		return self.sum(i + 1) - self.sum(i)

	def set(self, i, val):
		self.add(i, val - self.get(i))
(n, T) = map(int, input().split())
root = 0
for i in range(n):
	root ^= i
A = [[] for i in range(n)]
for _ in range(n - 1):
	(f, c) = map(int, input().split())
	A[f - 1] += (c - 1,)
	root ^= c - 1
fen = Fenwick(n)
rep = 0
from collections import deque
dq = deque([root])
while dq:
	s = dq.pop()
	if s < 0:
		fen.set(~s, 0)
	else:
		dq += (~s,)
		rep += fen.sum(min(n, s + T + 1)) - fen.sum(max(0, s - T))
		fen.set(s, 1)
		for i in A[s]:
			dq += (i,)
print(rep)


import sys

class FenwickTree:

	def __init__(self, size):
		self.array = [0] * size

	def add(self, index, value):
		assert index > 0 and index < len(self.array)
		while index < len(self.array):
			self.array[index] += value
			index += index & -index

	def sum(self, index):
		assert index >= 0 and index < len(self.array)
		total = 0
		while index != 0:
			total += self.array[index]
			index -= index & -index
		return total
(n, t) = tuple((int(i) for i in sys.stdin.readline().split()))
root = None
edges = tuple(([] for i in range(n + 1)))
for i in range(n - 1):
	(parent, child) = tuple((int(x) for x in sys.stdin.readline().split()))
	if root is None:
		root = parent
	edges[parent].append(child)
tree = FenwickTree(n + 1)
edge_index = [0] * (n + 1)
count = 0
path = [root]
popped = False
while len(path) > 0:
	vertex = path[-1]
	if popped:
		tree.add(vertex, -1)
	else:
		low_bound = max(vertex - t - 1, 0)
		high_bound = min(vertex + t, n)
		count += tree.sum(high_bound) - tree.sum(low_bound)
	if edge_index[vertex] < len(edges[vertex]):
		child = edges[vertex][edge_index[vertex]]
		tree.add(vertex, 1)
		path.append(child)
		edge_index[vertex] += 1
		popped = False
	else:
		path.pop()
		popped = True
print(count)


def build(a, i, j):
	if j - i == 1:
		return [a[i], None, None, i, j]
	l = j - i
	rl = build(a, i, i + l // 2)
	rr = build(a, i + l // 2, j)
	return [rl[0] + rr[0], rl, rr, i, j]

def update(r, i, k):
	if r is None or i < r[3] or i >= r[4]:
		return
	r[0] += k
	m = (r[3] + r[4]) // 2
	if i < m:
		update(r[1], i, k)
	else:
		update(r[2], i, k)

def get_sum(r, i, j):
	if r is None or j < r[3] or i > r[4]:
		return 0
	if i <= r[3] and j >= r[4]:
		return r[0]
	return get_sum(r[1], i, j) + get_sum(r[2], i, j)

def print_tr(a, pr=''):
	if a is None:
		return
	print(pr, a[0], a[3], a[4])
	print_tr(a[1], pr + '   ')
	print_tr(a[2], pr + '   ')

def dfs(g, a, r, k):
	st = []
	st.append([r, -1, 0])
	res = 0
	while len(st) > 0:
		v = st[-1]
		r = v[0]
		if v[1] != -1 and v[2] == 0:
			update(a, v[1], 1)
		if v[2] == 0:
			inc = get_sum(a, r - k, r + k + 1)
			res += inc
			st[-1][2] = 1
		f = False
		for i in g.get(r, []):
			st.append([i, v[0], False])
			g[r].remove(i)
			f = True
			break
		if f:
			continue
		if r not in g or len(g[r]) == 0:
			st.pop()
			if v[1] != -1 and v[2] == 1:
				update(a, v[1], -1)
				v[2] = 2
	return res
(n, k) = (int(x) for x in input().split(' '))
g = {}
a = [0 for x in range(n + 1)]
for i in range(n - 1):
	(p1, p2) = (int(x) for x in input().split(' '))
	a[p2] = p1
	if p1 in g:
		g[p1].append(p2)
	else:
		g[p1] = [p2]
r = 1
for i in range(1, n + 1):
	if a[i] == 0:
		r = i
		break
a = [0 for x in range(n + 1)]
b = build(a, 0, n + 1)
res = dfs(g, b, r, k)
print(res)


(N, K) = map(int, input().split())
children = [[] for i in range(N + 1)]
parent = [0] * (N + 1)
for i in range(1, N):
	(p, c) = map(int, input().split())
	children[p].append(c)
	parent[c] = p
fenwick = [0] * (N + 1)

def fenwick_add(i, x):
	while i <= N:
		fenwick[i] += x
		i += i & -i

def fenwick_sum(i):
	if i <= 0:
		return 0
	if i > N:
		i = N
	x = 0
	while i:
		x += fenwick[i]
		i &= i - 1
	return x
root = 1
while parent[root]:
	root = parent[root]
first = [1] * (N + 1)
active = [root]
pairs = 0
while len(active):
	i = active[-1]
	if first[i]:
		first[i] = 0
		active.extend(children[i])
		pairs += fenwick_sum(i + K) - fenwick_sum(i - K - 1)
		fenwick_add(i, 1)
	else:
		active.pop()
		fenwick_add(i, -1)
print(pairs)


def readints():
	return [int(fld) for fld in input().strip().split()]

def readtree(n):
	parent = [None] * (n + 1)
	children = [[] for _ in range(n + 1)]
	for _ in range(1, n):
		(p, c) = readints()
		parent[c] = p
		children[p].append(c)
	assert parent.count(None) == 2
	root = parent.index(None, 1)
	return (root, children)

def countsimilar_recursive(root, children, k, bitree=None):
	if bitree is None:
		bitree = [0] * len(children)
	count = sumupto(min(len(bitree) - 1, root + k), bitree) - sumupto(max(0, root - k - 1), bitree)
	addentry(root, 1, bitree)
	count += sum((countsimilar(child, children, k, bitree) for child in children[root]))
	addentry(root, -1, bitree)
	return count

def countsimilar(root, children, k):
	bitree = [0] * len(children)
	stack = [(root, True)]
	count = 0
	while stack:
		(root, starting) = stack.pop()
		if starting:
			count += sumupto(min(len(bitree) - 1, root + k), bitree) - sumupto(max(0, root - k - 1), bitree)
			addentry(root, 1, bitree)
			stack.append((root, False))
			stack.extend(((child, True) for child in children[root]))
		else:
			addentry(root, -1, bitree)
	return count

def addentry(idx, amt, bitree):
	bitree[idx] += amt
	pos = idx & ~(idx - 1)
	while True:
		if pos & idx:
			idx -= pos
		elif pos + idx < len(bitree):
			bitree[pos + idx] += amt
		else:
			break
		pos <<= 1

def sumupto(idx, bitree):
	count = 0
	while idx > 0:
		count += bitree[idx]
		idx = idx & idx - 1
	return count

def main():
	(n, k) = readints()
	(root, children) = readtree(n)
	print(countsimilar(root, children, k))
main()


__author__ = 'chrisgreening'
import collections

class Bit:

	def __init__(self, n):
		sz = 1
		while n >= sz:
			sz *= 2
		self.size = sz
		self.data = [0] * sz

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i < self.size:
			self.data[i] += x
			i += i & -i
(n, k) = [int(i) for i in input().strip().split(' ')]
children = [[] for i in range(n + 1)]
bit = Bit(n + k)

def dfs(node):
	count = 0
	count_upper = bit.sum(node + k)
	count_lower = bit.sum(node - k - 1)
	count += count_upper - count_lower
	bit.add(node, 1)
	if node in children:
		for child in children[node]:
			count += dfs(child)
	bit.add(node, -1)
	return count

class Entry:

	def __init__(self, node, children, added):
		self.node = node
		self.children = children
		self.added = added

def dfs2(node):
	count = 0
	frontier = [Entry(node, children[node], False)]
	while len(frontier) > 0:
		if not frontier[-1].added:
			count_upper = bit.sum(frontier[-1].node + k)
			count_lower = bit.sum(frontier[-1].node - k - 1)
			count += count_upper - count_lower
			bit.add(frontier[-1].node, 1)
			frontier[-1].added = True
		if len(frontier[-1].children) > 0:
			child = frontier[-1].children.pop()
			frontier.append(Entry(child, children[child], False))
		else:
			bit.add(frontier[-1].node, -1)
			frontier.pop()
	return count
root = -1
for _ in range(n - 1):
	(parent, child) = [int(i) for i in input().strip().split(' ')]
	if root == -1:
		root = parent
	children[parent].append(child)
print(dfs2(root))


import sys, resource
sys.setrecursionlimit(200000)
resource.setrlimit(resource.RLIMIT_STACK, (resource.RLIM_INFINITY, resource.RLIM_INFINITY))

def fenadd(seq, i, v):
	i += 1
	size = len(seq)
	while i <= size:
		seq[i - 1] += v
		i += i & -i

def fensum(seq, i):
	res = 0
	while i:
		res += seq[i - 1]
		i -= i & -i
	return res

def fensumrange(seq, i, j):
	return fensum(seq, j) - fensum(seq, i)
(n, k) = map(int, input().split())
links = [[] for i in range(n)]
(root, c) = (int(s) - 1 for s in input().split())
links[root].append(c)
for i in range(n - 2):
	(p, c) = (int(s) - 1 for s in input().split())
	links[p].append(c)
fenlist = [0] * n

def similar(i):
	res = fensumrange(fenlist, max(0, i - k), min(n, i + k + 1))
	fenadd(fenlist, i, 1)
	res += sum((similar(j) for j in links[i]))
	fenadd(fenlist, i, -1)
	return res
print(similar(root))


import bisect

class BinTree:

	def __init__(self):
		self.branch = []
		self.val = []

	def BuildTree(self, Val, QList, BranchCount, nm1):
		self.Val = [Val]
		while True:
			Breakout = True
			StartLoc = bisect.bisect_left(QList, (self.Val[-1], 0))
			if BranchCount.get(self.Val[-1]) != None:
				if BranchCount[self.Val[-1]] == 1:
					Breakout = False
					self.Val.append(QList[StartLoc][1])
				elif StartLoc <= nm1:
					for i in range(StartLoc, StartLoc + BranchCount[self.Val[-1]]):
						self.branch.append(BinTree())
						self.branch[-1].BuildTree(QList[i][1], QList, BranchCount, nm1)
			if Breakout:
				break
		self.Val.sort()

	def SearchDifference(self, k, RunningList=[]):
		nBranch = len(self.branch)
		nVal = len(self.Val)
		InsLoc = bisect.bisect_left(RunningList, self.Val[0])
		RLPass = RunningList[:InsLoc] + [self.Val[0]] + RunningList[InsLoc:]
		Count = bisect.bisect_right(RunningList, self.Val[0] + k) - bisect.bisect_left(RunningList, self.Val[0] - k)
		for Vi in self.Val[1:]:
			InsLoc = bisect.bisect_left(RLPass, Vi)
			Count += bisect.bisect_right(RLPass, Vi + k) - bisect.bisect_left(RLPass, Vi - k)
			RLPass.insert(InsLoc, Vi)
		if len(self.branch) > 0:
			for I in range(len(self.branch)):
				Count += self.branch[I].SearchDifference(k, RLPass)
		return Count
(n, k) = [int(m) for m in input().strip().split()]
QList = []
RootList = []
for i in range(n - 1):
	(A1, A2) = [int(m) for m in input().strip().split()]
	QList.append((A1, A2))
	RootList.append(A1)
BranchCount = {m: 0 for m in set(RootList)}
for i in RootList:
	BranchCount[i] += 1
Root = QList[0][0]
QList.sort()
Tree = BinTree()
Tree.BuildTree(Root, QList, BranchCount, n - 1)
print(Tree.SearchDifference(k))


def set(tree, i, val):
	while i <= N:
		tree[i] += val
		i += i & -i

def bit_sum(tree, i):
	res = 0
	while i > 0:
		res += tree[i]
		i -= i & -i
	return res

def similarity(tree, bit_tree, root):
	from collections import deque
	stack = deque()
	stack.append((root, []))
	acc = 0
	while stack:
		(node, ancestors) = stack.pop()
		acc += bit_sum(bit_tree, min(N, node + K)) - bit_sum(bit_tree, max(1, node - K) - 1)
		set(bit_tree, node, 1)
		children = tree[node]
		if children:
			iterchild = iter(children)
			ancestors.append(node)
			stack.append((next(iterchild), ancestors))
			for child in iterchild:
				stack.append((child, []))
		else:
			for ancestor in ancestors:
				set(bit_tree, ancestor, -1)
			set(bit_tree, node, -1)
	return acc
(N, K) = map(lambda x: int(x), input().split(' '))
tree = list([[] for _ in range(N + 1)])
(root, child) = map(lambda x: int(x), input().split(' '))
tree[root].append(child)
for _ in range(N - 2):
	line = input().split(' ')
	parent = int(line[0])
	child = int(line[1])
	tree[parent].append(child)
print(similarity(tree, [0] * (N + 1), root))


import sys
import math
sys.setrecursionlimit(200000)
(n, k) = [int(s) for s in input().split(' ')]
adj = [[] for i in range(n + 1)]
root = 0
for i in range(n - 1):
	(p, c) = [int(s) for s in input().split(' ')]
	adj[p].append(c)
	if root == 0:
		root = p
	elif root == c:
		root = p

def rmq_update(rmq, st, en, i, val, index):
	if st == i and en == i:
		rmq[index] += val
		return rmq[index]
	if i < st or i > en:
		return rmq[index]
	mid = (st + en) // 2
	rmq[index] = rmq_update(rmq, st, mid, i, val, 2 * index + 1) + rmq_update(rmq, mid + 1, en, i, val, 2 * index + 2)
	return rmq[index]

def rmq_calc(rmq, st, en, i, j, index):
	if i <= st and j >= en:
		return rmq[index]
	if j < st or i > en:
		return 0
	mid = (st + en) // 2
	return rmq_calc(rmq, st, mid, i, j, 2 * index + 1) + rmq_calc(rmq, mid + 1, en, i, j, 2 * index + 2)

def dfs(v, k, nmax, adj, rmq, res):
	i = max(0, v - k)
	j = min(nmax - 1, v + k)
	left = rmq_calc(rmq, 0, nmax - 1, i, j, 0)
	res[0] += left
	rmq_update(rmq, 0, nmax - 1, v, 1, 0)
	for c in adj[v]:
		dfs(c, k, nmax, adj, rmq, res)
	rmq_update(rmq, 0, nmax - 1, v, -1, 0)
	pass

def dfs_flat(n, k, nmax, adj, root, rmq):
	st = [root]
	res = 0
	used = [False] * (n + 1)
	while len(st) > 0:
		v = st[-1]
		if not used[v]:
			rmq_update(rmq, 0, nmax - 1, v, 1, 0)
			used[v] = True
		if len(adj[v]) == 0:
			del st[-1]
			i = max(0, v - k)
			j = min(nmax - 1, v + k)
			left = rmq_calc(rmq, 0, nmax - 1, i, j, 0) - 1
			res += left
			rmq_update(rmq, 0, nmax - 1, v, -1, 0)
		else:
			c = adj[v][-1]
			st.append(c)
			del adj[v][-1]
	return res

def solve(n, k, adj, root):
	nmax = n + 1
	rsize = math.ceil(math.log(nmax, 2))
	rsize = 2 * 2 ** rsize - 1
	rmq = [0] * rsize
	res = [0]
	res = dfs_flat(n, k, nmax, adj, root, rmq)
	return res
res = solve(n, k, adj, root)
print(res)


import collections

class TreeArray:

	def lowbit(self, x):
		return x & -x

	def __init__(self, n):
		self.a = [0 for _ in range(n + 1)]

	def add(self, i, val):
		while i < len(self.a):
			self.a[i] += val
			i += self.lowbit(i)

	def query(self, i, j):
		ret = 0
		while j > 0:
			ret += self.a[j]
			j -= self.lowbit(j)
		i -= 1
		while i > 0:
			ret -= self.a[i]
			i -= self.lowbit(i)
		return ret

def main():
	line = input()
	n = int(line.strip().split(' ')[0])
	k = int(line.strip().split(' ')[1])
	graph = [collections.deque() for _ in range(n + 1)]
	degree = [0 for _ in range(n + 1)]
	for _ in range(n - 1):
		line = input()
		p = int(line.strip().split(' ')[0])
		c = int(line.strip().split(' ')[1])
		graph[p].append(c)
		degree[c] = 1
	for i in range(1, n + 1):
		if degree[i] == 0:
			root = i
			break
	arr = TreeArray(n)
	stack = collections.deque()
	stack.append((root, -1, 0))
	retval = None
	while len(stack) > 0:
		(root, idx, val) = stack.pop()
		if idx == -1:
			arr.add(root, 1)
		else:
			val += retval
		idx += 1
		if idx < len(graph[root]):
			stack.append((root, idx, val))
			stack.append((graph[root][idx], -1, 0))
		else:
			arr.add(root, -1)
			retval = val + arr.query(max(1, root - k), min(n, root + k))
	print(retval)
main()


import sys

def update(fw, i, d):
	n = len(fw)
	while i <= n:
		fw[i] += d
		i += i & -i

def diff(fw, a, b):
	u = 0
	while b:
		u += fw[b]
		b -= b & -b
	while a:
		u -= fw[a]
		a -= a & -a
	return u

def similar(line):
	(n, K) = map(int, next(line).split())
	root = set(range(1, n - 1))
	tree = {}
	for x in range(n - 1):
		(a, b) = map(int, next(line).split())
		root -= {b}
		tree[a] = tree.get(a, []) + [b]
	root = list(root)
	stack = [iter(root)]
	visited = [True] * (n + 1)
	fw = [0] * (n + 2)
	cnt = 0
	while stack:
		for id in stack[-1]:
			if visited[id]:
				cnt += diff(fw, max(0, id - K - 1), min(n, id + K))
				visited[id] = False
				if id in tree:
					root.append(id)
					stack.append(iter(tree[id]))
					update(fw, id, 1)
				break
		else:
			update(fw, root.pop(), -1)
			stack.pop()
	print(cnt)
similar(sys.stdin)


def set(tree, i, val):
	while i <= N:
		tree[i] += val
		i += i & -i

def bit_sum(tree, i):
	res = 0
	while i > 0:
		res += tree[i]
		i -= i & -i
	return res

def similarity(tree, bit_tree, root):
	from collections import deque
	stack = deque()
	stack.append((root, []))
	acc = 0
	while stack:
		(node, ancestors) = stack.pop()
		acc += bit_sum(bit_tree, min(N, node + K)) - bit_sum(bit_tree, max(1, node - K) - 1)
		set(bit_tree, node, 1)
		children = tree[node]
		if children:
			iterchild = iter(children)
			ancestors.append(node)
			stack.append((next(iterchild), ancestors))
			for child in iterchild:
				stack.append((child, []))
		else:
			for ancestor in ancestors:
				set(bit_tree, ancestor, -1)
			set(bit_tree, node, -1)
	return acc
(N, K) = map(lambda x: int(x), input().split(' '))
tree = list([[] for _ in range(N + 1)])
(root, child) = map(lambda x: int(x), input().split(' '))
tree[root].append(child)
for _ in range(N - 2):
	line = input().split(' ')
	parent = int(line[0])
	child = int(line[1])
	tree[parent].append(child)
print(similarity(tree, [0] * (N + 1), root))


(N, K) = map(int, input().split())
children = [[] for i in range(N + 1)]
parent = [0] * (N + 1)
for i in range(1, N):
	(p, c) = map(int, input().split())
	children[p].append(c)
	parent[c] = p
fenwick = [0] * (N + 1)

def fenwick_add(i, x):
	while i <= N:
		fenwick[i] += x
		i += i & -i

def fenwick_sum(i):
	if i <= 0:
		return 0
	if i > N:
		i = N
	x = 0
	while i:
		x += fenwick[i]
		i &= i - 1
	return x
root = 1
while parent[root]:
	root = parent[root]
first = [1] * (N + 1)
active = [root]
pairs = 0
while len(active):
	i = active[-1]
	if first[i]:
		first[i] = 0
		active.extend(children[i])
		pairs += fenwick_sum(i + K) - fenwick_sum(i - K - 1)
		fenwick_add(i, 1)
	else:
		active.pop()
		fenwick_add(i, -1)
print(pairs)


from collections import OrderedDict
import sys
import json
sys.setrecursionlimit(1500)
values = list(sys.stdin)
(N, T) = [int(val) for val in values[0].split()]
graph = [None] * (N + 1)
tree = [0] * ((N + 1) * 4)
degs = [0] * (N + 1)

def query(index, left, right, begin, end):
	stack = [(index, left, right, begin, end)]
	append = stack.append
	vals = []
	add_val = vals.append
	while stack:
		(index, left, right, begin, end) = stack.pop()
		if right < begin or left > end:
			add_val(0)
			continue
		if left <= begin and right >= end:
			add_val(tree[index])
			continue
		mid = int(begin + (end - begin) / 2)
		append((index * 2, left, right, begin, mid))
		append((index * 2 + 1, left, right, mid + 1, end))
		continue
	return sum(vals)

def update(index, node, val, begin, end):
	stack = []
	append = stack.append
	append((index, node, val, begin, end))
	while stack:
		(index, node, val, begin, end) = stack.pop()
		if node < begin or node > end:
			continue
		if begin <= node and node <= end:
			tree[index] += val
		if begin == node and end == node:
			continue
		mid = int(begin + (end - begin) / 2)
		append((index * 2, node, val, begin, mid))
		append((index * 2 + 1, node, val, mid + 1, end))

def find_pairs(root):
	stack = [(root, (1, root, -1, 1, N))]
	append = stack.append
	sims = []
	add_sim = sims.append
	while stack:
		(root, next) = stack.pop()
		if root == None:
			update(*next)
			continue
		l = max(1, root - T)
		r = min(N, root + T)
		sim = query(1, l, r, 1, N)
		add_sim(sim)
		update(1, root, 1, 1, N)
		next_roots = graph[root]
		append((None, (1, root, -1, 1, N)))
		if next_roots:
			for deg in graph[root]:
				append((deg, None))
	return sum(sims)

def add_node(si, ei):
	si = int(si)
	ei = int(ei)
	try:
		graph[si].append(ei)
	except AttributeError:
		graph[si] = [ei]
	degs[ei] += 1
[add_node(*line.split()) for line in values[1:]]
root = -1
for (i, deg) in enumerate(degs[1:]):
	if deg == 0:
		root = i + 1
		break
print(find_pairs(root))


from collections import OrderedDict
import sys
import json
sys.setrecursionlimit(1500)
values = list(sys.stdin)
(N, T) = [int(val) for val in values[0].split()]
graph = [None] * (N + 1)
tree = [0] * ((N + 1) * 4)
degs = [0] * (N + 1)

def query(index, left, right, begin, end):
	stack = [(index, left, right, begin, end)]
	append = stack.append
	vals = []
	add_val = vals.append
	while stack:
		(index, left, right, begin, end) = stack.pop()
		if right < begin or left > end:
			add_val(0)
			continue
		if left <= begin and right >= end:
			add_val(tree[index])
			continue
		mid = int(begin + (end - begin) / 2)
		append((index * 2, left, right, begin, mid))
		append((index * 2 + 1, left, right, mid + 1, end))
		continue
	return sum(vals)

def update(index, node, val, begin, end):
	stack = []
	append = stack.append
	append((index, node, val, begin, end))
	while stack:
		(index, node, val, begin, end) = stack.pop()
		if node < begin or node > end:
			continue
		if begin <= node and node <= end:
			tree[index] += val
		if begin == node and end == node:
			continue
		mid = int(begin + (end - begin) / 2)
		append((index * 2, node, val, begin, mid))
		append((index * 2 + 1, node, val, mid + 1, end))

def find_pairs(root):
	stack = [(root, (1, root, -1, 1, N))]
	append = stack.append
	sims = []
	add_sim = sims.append
	while stack:
		(root, next) = stack.pop()
		if root == None:
			update(*next)
			continue
		l = max(1, root - T)
		r = min(N, root + T)
		sim = query(1, l, r, 1, N)
		add_sim(sim)
		update(1, root, 1, 1, N)
		next_roots = graph[root]
		append((None, (1, root, -1, 1, N)))
		if next_roots:
			for deg in graph[root]:
				append((deg, None))
	return sum(sims)

def add_node(si, ei):
	si = int(si)
	ei = int(ei)
	try:
		graph[si].append(ei)
	except AttributeError:
		graph[si] = [ei]
	degs[ei] += 1
[add_node(*line.split()) for line in values[1:]]
root = -1
for (i, deg) in enumerate(degs[1:]):
	if deg == 0:
		root = i + 1
		break
print(find_pairs(root))