Canadian Computing Competition: 2010 Stage 2, Day 1, Problem 2
We are given a rooted tree with ~N~ nodes in which each node has at most two children. Each node may be black or white. We define a "prune" as the deletion of a node and the subtree rooted at that node from the tree. Given an integer ~D~, find the minimum number of "prunes" required to obtain a tree in which the number of white nodes minus the number of black nodes is exactly ~D~, or determine that it is impossible to do so.
The first line of input will contain two integers ~N~ ~(1 \le N \le 300)~ and ~D~ ~(-N \le D \le N)~, representing the number of nodes in the tree and the required difference, respectively. The next ~N~ blocks of input each contain the description of a node. The first line of each block contains three integers: the id of the node (a unique integer between ~0~ and ~N-1~), the colour of the node (
1 for a white node,
0 for a black node) and an integer ~C~ that represents the number of children of the node. ~C~ lines follow, each one containing an integer that represents the id of one child. The root of the tree is the node with id ~0~.
On one line, output the minimum number of "prunes", as mentioned in the problem description. If it is impossible to obtain the required difference ~D~, output
6 3 0 1 2 1 3 1 1 2 2 5 2 1 1 4 3 1 0 4 0 0 5 1 0