Trimming the Tree
InterviewTime limit1sMemory limit1024 MB
Given a tree rooted at node 1 and a limit K per level, remove subtrees so that each level keeps at most K nodes, and find the maximum number of nodes kept.
Problem
In the country where Dongbin lives, trees are shaped like trees.
As Christmas approaches, Dongbin decides to trim a tree and decorate it at home.
Dongbin's tree has N nodes connected by N-1 edges. Nodes are numbered from 1 to N, and the root node is 1.
In the tree, the root has level 0, and the level increases by 1 with each step down. Dongbin wants to decorate every node, but if the thickness of the tree exceeds K, the tree does not fit in the house.
Here, the thickness of the tree is the maximum number of nodes on the same level.
In the end, some nodes must be removed so that the thickness is at most K. When a parent node is removed, all of its child nodes are removed too.
Dongbin wants as many decorations as possible, so he wants to keep as many nodes as possible. Help Dongbin.
Input
The first line contains the number of vertices N and the maximum number of nodes K that can be kept on each level. (1 ≤ N ≤ 10,000, 1 ≤ K ≤ N)
Each of the next N-1 lines contains two integers a**i and bi. This means node ai and node bi are connected by an edge. (1 ≤ ai, bi ≤ N, ai ≠ bi)
Output
Print the number of nodes that remain after trimming the tree while keeping as many nodes as possible.