CCO '10 P2 - Tree Pruning

View as PDF

Submit solution

Points: 15
Time limit: 2.0s
Memory limit: 256M

Problem type
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.

Input Specification

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.

Output Specification

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 -1.

Sample Input

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

Sample Output

1

Comments


  • 0
    Roronoa_Zoro1540  commented on Jan. 27, 2018, 7:17 p.m.

    does it guarantee that the nodes inputted will be in the order 0, 1, 2.. N - 1?