# Cut Tree

# Cut Tree

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.