Minimizing Tree Weight

We are given a tree with \( n \) nodes and \( n-1 \) edges forming an undirected connected graph. Initially, every node is white. Your task is to choose exactly \( k \) nodes to color black so that the following objective is minimized:

For any edge, if you remove it, the tree splits into two connected components which contain \( b_1 \) and \( b_2 \) black nodes respectively. The weight of that edge is defined as \( |b_1 - b_2| \) (in \( \LaTeX \) this is given by \( |b_1 - b_2| \)). The weight of the tree is the sum of the weights of all edges. Compute the minimum possible weight.

Hint: If you root the tree arbitrarily (say at node 1), then for an edge connecting a node with its parent, suppose the subtree has \( m \) black nodes. Then the edge weight can be computed as \( |2m - k| \) because the other part will have \( k-m \) black nodes. You can use dynamic programming on trees to solve this problem.

inputFormat

The first line contains two integers \( n \) and \( k \) (with \( 1 \le n \le 200 \) and \( 0 \le k \le n \)). Each of the next \( n-1 \) lines contains two integers \( u \) and \( v \) indicating an edge connecting nodes \( u \) and \( v \) in the tree.

outputFormat

Output a single integer: the minimum possible weight of the tree.

sample

2 1
1 2

1