TheKingsTree
SRM 643 · 2014-08-25 · by Witaliy
Problem Statement
The King of Byteland is going to decorate a rooted tree. The tree has N vertices, numbered 0 through N-1. Vertex 0 is the root of the tree.
You are given the description of the tree in a
Each vertex of the tree must be painted in one of two colors: red or green. After the entire tree has been painted we can compute the cost of the painting. For each i, the cost of painting vertex i is defined as the number of vertices that are in the subtree rooted at i and have the same color as vertex i. For example, if a vertex is red and all other vertices in its subtree are green, the cost of painting this vertex is 1. The cost of painting the entire tree is the sum of all costs of painting its vertices.
Return the minimum cost of painting the given tree.
Constraints
- N will be between 1 and 50, inclusive.
- parent will contain exactly N-1 elements.
- For each i, parent[i] will be between 0 and i, inclusive.
{0, 0, 0}
Returns: 4
The root vertex 0 has three children: vertices 1, 2, and 3. One optimal way to color this tree is to color all three children red and their parent green.
{0, 1, 2, 3, 4}
Returns: 12
Color any three vertices green and the other three red.
{0, 1, 1, 1, 2, 0, 0, 5, 2, 9, 8, 1, 12, 4, 3, 10, 16, 13, 12, 7, 11, 17, 18, 14, 23, 20, 6, 3, 17, 13, 1, 13}
Returns: 70
{0, 1, 2, 3, 1}
Returns: 10
{0, 0, 0, 2, 2, 1, 2, 0, 5, 4, 4, 11, 2, 0, 3, 10, 5, 3, 13, 10, 9, 7, 5, 11, 19, 19, 3, 25, 27, 11, 5, 16, 18, 10, 8, 9, 3, 4, 33, 30, 7}
Returns: 72
Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheKingsTree with a public method int getNumber(vector<int> parent) · 82 test cases · 2 s / 256 MB per case