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. def cutTree(n, k, edges): g = [[] for _ in range(n)] for i in edges: g[i[0]-1].append(i[1]-1) g[i[1]-1].append(i[0]-1) global ans ans = 1 def multiply(x, y): ans = defaultdict(lambda: 0) for k, v in x.items(): for k1, v1 in y.items(): ans[k+k1-1] += v*v1 for k, v in ans.items(): if k in x: x[k] += v else: x[k] = v def dfs(i,p): global ans if g == [p]: ans += 1 return {0:1} x = 1 if i else 0 res = {len(g)-x : 1} for nxt in g: if nxt != p: multiply(res, dfs(nxt, i)) ans += sum(((v if i+x <= k else 0) for i, v in res.items())) return res dfs(0,-1) return ans It solves https://www.hackerrank.com/challenges/cuttree/forum but how? Continue reading...
