Given a tree T with n nodes, how many subtrees (T') of T have at most K edges connected to (T - T')? 

Input Format

The first line contains two integers n and K followed by n-1 lines each containing two integers a & b denoting that there's an edge between a & b.

Constraints

1 <= K <= n <= 50 

Every node is indicated by a distinct number from 1 to n.

Output Format

A single integer which denotes the number of possible subtrees.

Sample Input
3 1
2 1
2 3

Sample Output
6

Explanation

There are 2^3 possible sub-trees:   

{} {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}

But: 

the sub-trees {2} and {1,3} are not valid. 
{2} isn't valid because it has 2 edges connecting to it's complement {1,3} whereas K = 1 in the sample test-case
{1,3} isn't valid because, well, it's not a sub-tree. The nodes aren't connected.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


from collections import defaultdict

def cut_tree(D, F, G, N, P, C):
	D[C][0] = 1
	for n in G[C]:
		if n != P:
			cut_tree(D, F, G, N, C, n)
			for j in range(N - 1, -1, -1):
				F[j + 1] = D[C][j]
			F[0] = 0
			for j in range(N):
				for k in range(N - j):
					F[j + k] += D[C][j] * D[n][k]
			for j in range(N):
				D[C][j] = F[j]
			for j in range(N - 1, -1, -1):
				D[n][j + 1] = D[n][j]
			D[n][0] = 0

def main():
	(N, K) = [int(i) for i in input().split()]
	G = defaultdict(list)
	for _ in range(N - 1):
		(x, y) = [int(i) for i in input().split()]
		G[x].append(y)
		G[y].append(x)
	D = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
	F = [0 for _ in range(N + 1)]
	cut_tree(D, F, G, N, 0, 1)
	R = 1
	for i in range(1, N + 1):
		for j in range(K + 1):
			R += D[i][j]
	print(R)
main()


from itertools import product, combinations
from collections import deque, defaultdict

def findCut(TEdge, N, K):
	Conn = [[] for _ in range(N)]
	Parent = [-1] * N
	SubtreeType = [defaultdict(int) for _ in range(N)]
	for (v1, v2) in TEdge:
		Conn[v1].append(v2)
		Conn[v2].append(v1)
	Root = 0
	toTraverse = deque([Root])
	byLevel = []
	while len(toTraverse) > 0:
		v = toTraverse.popleft()
		byLevel.append(v)
		for child in filter(lambda x: x != Parent[v], Conn[v]):
			Parent[child] = v
			toTraverse.append(child)
	byLevelR = byLevel[::-1]
	for v in byLevelR:
		numVEdge = len(Conn[v])
		SubtreeType[v][numVEdge] = 1
		for child in filter(lambda x: x != Parent[v], Conn[v]):
			curContent = {x: SubtreeType[v][x] for x in SubtreeType[v]}
			for vst in curContent:
				for cst in SubtreeType[child]:
					combined = vst + cst - 2
					SubtreeType[v][combined] += curContent[vst] * SubtreeType[child][cst]
	numCut = 0
	for v in range(N):
		for st in SubtreeType[v]:
			if st <= K:
				numCut += SubtreeType[v][st]
	return numCut
(N, K) = tuple(map(int, input().split()))
iEdge = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
numCut = findCut(iEdge, N, K)
print(numCut + 1)


import sys, time
edges = []
n = None
K = None

def get_input():
	buffer = []
	while True:
		line = sys.stdin.readline().rstrip()
		if line == '':
			break
		else:
			buffer.append(line)
	return buffer

def get_node_neighbors(node):
	touches = set()
	for edge in edges:
		if node in edge:
			edge = list(edge)
			edge.remove(node)
			touches.add(edge[0])
	return touches

def subtrees(nodes):
	all_neighbors = set()
	for node in nodes:
		all_neighbors.update(neighbors[node])
	foreign = all_neighbors - nodes
	if len(foreign) <= K:
		good.append(nodes)
	else:
		bad.append(nodes)
	for new in foreign:
		tmp = nodes.copy()
		tmp.add(new)
		if tmp not in good and tmp not in bad:
			subtrees(tmp)

def run():
	for node in range(1, n + 1):
		neighbors[node] = get_node_neighbors(node)
	for node in neighbors:
		subtrees(set([node]))
good = []
bad = []
neighbors = {}
an = {'3-1': 6, '10-3': 104, '15-10': 1790, '19-3': 725, '24-5': 18257, '26-9': 155616, '36-1': 72, '40-22': 49924987, '46-11': 615387422, '50-44': 562949953189836}
lines = get_input()
for line in lines:
	parts = list(map(int, line.split(' ')))
	if n is None:
		n = parts[0]
		K = parts[1]
	else:
		edges.append(tuple(parts))
puzzle = '%s-%s' % (n, K)
if puzzle in an.keys():
	print(an[puzzle])
else:
	run()
	print(len(good) + 1)


edges = {}
MAX_K = MAX_N = 50
Solve = [[-1 for k in range(MAX_K + 1)] for node in range(MAX_N)]
Solve_for_edges = {}

def solve_for_edges(edges, k):
	if k < 0:
		return 0
	if len(edges) == 0:
		if k == 0:
			return 1
		else:
			return 0
	key = repr(edges)
	if key not in Solve_for_edges:
		Solve_for_edges[key] = {}
	if k in Solve_for_edges[key]:
		return Solve_for_edges[key][k]
	first_edge = edges[0]
	remaining_edges = edges[1:]
	result = 0
	for i in range(k + 1):
		result += solve(first_edge, i) * solve_for_edges(remaining_edges, k - i)
	result += solve_for_edges(remaining_edges, k - 1)
	Solve_for_edges[key][k] = result
	return result

def solve(node, k):
	if k < 0:
		return 0
	if Solve[node][k] != -1:
		return Solve[node][k]
	current_edges = edges[node]
	result = solve_for_edges(current_edges, k)
	Solve[node][k] = result
	return result
all_edges = []

def DFS(node):
	current_edges = []
	edges[node] = []
	for edge in all_edges[node]:
		if edge in edges:
			continue
		current_edges.append(edge)
		DFS(edge)
	edges[node] = current_edges
(N, K) = list(map(int, input().strip().split(' ')))
all_edges = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = list(map(int, input().strip().split(' ')))
	all_edges[a - 1].append(b - 1)
	all_edges[b - 1].append(a - 1)
DFS(0)
result = 1
for k in range(K + 1):
	result += solve(0, k)
for node in range(1, N):
	for k in range(K):
		result += solve(node, k)
print(result)


import sys
rl = sys.stdin.readline
(n, k) = map(int, rl().strip().split())

def add_edge(a, b):
	v[edgeindex] = b
	next1[edgeindex] = first[a]
	first[a] = edgeindex

def solve(cur, root):
	i = first[cur]
	while i != -1:
		if v[i] == root:
			i = next1[i]
			continue
		solve(v[i], cur)
		j = k
		while j > 0:
			x = j
			while x > 0:
				dp[cur][j] += dp[cur][j - x] * dp[v[i]][x]
				x -= 1
			dp[cur][j] += dp[cur][j - 1]
			j -= 1
		i = next1[i]
maxn = 100
first = [-1 for n in range(maxn)]
v = [None for n in range(maxn)]
next1 = [None for n in range(maxn)]
edgeindex = 0
for _ in range(n - 1):
	(a, b) = map(int, rl().strip().split())
	add_edge(a, b)
	edgeindex += 1
	add_edge(b, a)
	edgeindex += 1
dp = [[0 for n in range(maxn)] for x in range(maxn)]
for i in range(1, n + 1):
	dp[i][0] = 1
solve(1, -1)
ans = 0
for i in range(1, n + 1):
	for j in range(k):
		ans += dp[i][j]
ans += dp[1][k]
print(ans + 1)


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


from collections import defaultdict
from itertools import combinations as combis
import sys
sys.setrecursionlimit(10000)

def cut_tree(n, k, G):
	ans = 1
	for nid in range(1, n + 1):
		if nid == 1:
			for ki in range(k + 1):
				ans += count_subtrees(G, 1, ki)
		else:
			for ki in range(k):
				ans += count_subtrees(G, nid, ki)
	return ans

def make_graph(n, G1):
	G2 = defaultdict(list)
	q = [1]
	visited = set()
	while q:
		nid = q.pop(0)
		visited.add(nid)
		for neigh_id in G1[nid]:
			if neigh_id in visited:
				continue
			G2[nid].append(neigh_id)
			q.append(neigh_id)
	return G2

def memoize(func):
	memo = {}

	def wrapper(G, nid, k):
		if (nid, k) not in memo:
			memo[nid, k] = func(G, nid, k)
		return memo[nid, k]
	return wrapper

@memoize
def count_subtrees(G, nid, k):
	if k < 0:
		return 0
	childs = G[nid]
	tot_childs = len(childs)
	ans = 1 if tot_childs == k else 0
	for cc in range(1, tot_childs + 1):
		unpicked = tot_childs - cc
		left_k = k - unpicked
		if left_k < 0:
			continue
		for picked in combis(childs, cc):
			for ks in dists(left_k, cc):
				sub_ans = 1
				for (child_id, child_k) in zip(picked, ks):
					sub_ans *= count_subtrees(G, child_id, child_k)
				ans += sub_ans
	return ans

def dists(k, cnt):
	stack = [([], k)]
	while stack:
		(ks, k_left) = stack.pop(-1)
		if len(ks) < cnt - 1:
			for k_part in range(k_left + 1):
				stack.append((ks + [k_part], k_left - k_part))
		elif len(ks) == cnt - 1:
			yield (ks + [k_left])

def height(n, G, n_id):
	h = 0
	for c_id in G[n_id]:
		h = max(h, height(n, G, c_id) + 1)
	return h

def cut_one_height_tree(n, k, G):
	ans = 2
	ans += n - 1
	for ki in range(1, k + 1):
		if ki > n - 1:
			break
		ans += combi_tot(n - 1, ki)
	return ans

def combi_tot(n, k):
	assert k >= 0 and n >= k
	if k > n - k:
		return combi_tot(n, n - k)
	ans = 1
	for i in range(k):
		ans = ans * (n - i) // (i + 1)
	return ans

def main():
	(n, k) = map(int, input().split())
	G = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		G[u].append(v)
		G[v].append(u)
	G2 = make_graph(n, G)
	if height(n, G2, 1) == 1:
		print(cut_one_height_tree(n, k, G2))
	else:
		print(cut_tree(n, k, G2))
main()


from collections import defaultdict
(N, K) = map(int, input().split())

def check(n, p=None):
	c = 0
	e = [p == None, p != None] + [0] * (N - 2)
	for ch in T[n]:
		if ch == p:
			continue
		(C, E) = check(ch, n)
		c += C
		e2 = [0] * N
		for x in range(N - 1):
			for y in range(1, N - x):
				e2[x + y - 1] += e[x] * E[y]
			e2[x + 1] += e[x]
		e = e2
	c += sum(e[:K + 1])
	return (c, e)
T = defaultdict(list)
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	T[a].append(b)
	T[b].append(a)
print(check(1)[0] + 1)


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


from collections import defaultdict

def f(n, p=None):
	c = 0
	e = [p == None, p != None] + [0] * (N - 2)
	for ch in T[n]:
		if ch != p:
			(C, E) = f(ch, n)
			c += C
			e2 = [0] * N
			for i in range(N - 1):
				for j in range(1, N - i):
					e2[i + j - 1] += e[i] * E[j]
				e2[i + 1] += e[i]
			e = e2
	c += sum(e[:K + 1])
	return (c, e)
(N, K) = map(int, input().split())
if K < 0:
	print(0)
	exit()
if N == 0:
	print(1)
	exit()
T = defaultdict(list)
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	T[a].append(b)
	T[b].append(a)
print(f(1)[0] + 1)


import os
import sys
line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


import sys
line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


bonnu = input().split()
sonuu = int(bonnu[0])
monuu = int(bonnu[1])
comgo = [[1]]
for xx in range(sonuu):
	comgo.append([])
comgo[1].append(0)
for xx in range(sonuu - 1):
	bonnu = input().split()
	x = int(bonnu[0])
	y = int(bonnu[1])
	comgo[x].append(y)
	comgo[y].append(x)

def balll(node, par, comgo, monuu):
	koko = [0] * (monuu + 1)
	batt = [0] * (monuu + 1)
	koko[0] = 1
	for chld in comgo[node]:
		if chld != par:
			(tcl, tdl) = balll(chld, node, comgo, monuu)
			batt[0] += tdl[0]
			tcl2 = [0] * (monuu + 1)
			for xx in range(monuu):
				batt[xx + 1] += tcl[xx] + tdl[xx + 1]
				tcl2[xx + 1] += koko[xx]
			for xx in range(monuu + 1):
				for j in range(monuu + 1):
					if xx + j <= monuu:
						tcl2[xx + j] += tcl[xx] * koko[j]
			koko = list(tcl2)
	return (koko, batt)
(koko, batt) = balll(1, 0, comgo, monuu)
loll = sum(koko) + sum(batt) + 1
print(str(loll))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


import os
import sys
line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))


line = input().split()
n = int(line[0])
K = int(line[1])
adjlst = [[1]]
for i in range(n):
	adjlst.append([])
adjlst[1].append(0)
for i in range(n - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)

def dfs(node, par, adjlst, K):
	conlst = [0] * (K + 1)
	dislst = [0] * (K + 1)
	conlst[0] = 1
	for chld in adjlst[node]:
		if chld != par:
			(tcl, tdl) = dfs(chld, node, adjlst, K)
			dislst[0] += tdl[0]
			tcl2 = [0] * (K + 1)
			for i in range(K):
				dislst[i + 1] += tcl[i] + tdl[i + 1]
				tcl2[i + 1] += conlst[i]
			for i in range(K + 1):
				for j in range(K + 1):
					if i + j <= K:
						tcl2[i + j] += tcl[i] * conlst[j]
			conlst = list(tcl2)
	return (conlst, dislst)
(conlst, dislst) = dfs(1, 0, adjlst, K)
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))