Hi there,
I am not able to solve div-2 1000 problem of yesterday's srm 644. Please ,provide some hint to the direction in which I can proceed.
================================================================================================ TreeCutting Problem Statement
Wolf Sothe has an undirected tree with N vertices, numbered 0 through N-1. You are given the description of the tree as a int[] par with N-1 elements. For each valid i, the tree contains the edge between vertices (i+1) and par[i]. (Note that for your convenience par[i] is always smaller than i+1.)
Some of the vertices contain a positive integer, others are empty. You are given a int[] num with N elements. For each valid i, num[i] is either the number written in vertex i, or -1 if vertex i is empty.
Sothe can modify the tree by cutting some of its edges. Sothe's goal is to reach a configuration with the following properties: Each connected component contains exactly one vertex with an integer. The number of vertices in each component is equal to the only integer in that component.
Return "POSSIBLE" (quotes for clarity) if Sothe can reach some configuration with the desired properties by cutting zero or more edges. Otherwise, return "IMPOSSIBLE". Note that the return value is case-sensitive. Definition
Class TreeCutting Method can Parameters vector , vector Returns string Method signature string can(vector par, vector num) (be sure your method is public) Limits
Time limit (s) 2.000 Memory limit (MB) 256 Constraints
N will be between 1 and 50, inclusive. par will contain exactly N-1 elements. For each i, the i-th element of par will be between 0 and i, inclusive. num will contain exactly N elements. Each element in num will be either -1 or between 1 and N, inclusive. Test cases
par { 0, 1, 2, 2, 2 } num { 2, -1, -1, 4, -1, -1 } Returns "POSSIBLE" This is a tree with 6 vertices. The edges are 1-0, 2-1, 3-2, 4-2, and 5-2. Vertex 0 contains the integer 2, vertex 3 contains the integer 4, and all other vertices are empty.
Sothe can reach his goal by cutting the edge 1-2. This will produce two components. In one component we have the vertices {0,1}. One of them contains the number 2 (which is also the size of this component) and the other is empty. In the other component we have the vertices {2,3,4,5}. One of them contains the number 4 (which is also the size of this component) and the other three are empty. par { 0, 1, 2, 2, 2 } num { 3, -1, -1, 3, -1, -1 } Returns "IMPOSSIBLE" par { 0, 1, 2, 2, 2 } num { 2, -1, -1, 3, -1, -1 } Returns "IMPOSSIBLE" The tree has 6 vertices but in any valid final configuration the components must have 2+3 = 5 vertices, which is impossible. par { 0, 1, 2, 2, 1, 5, 2, 6, 6 } num { -1, -1, 2, -1, 1, 3, -1, 1, 1, 2 } Returns "POSSIBLE" par { 0, 1, 2, 2, 1, 5, 2, 6, 6 } num { -1, -1, 2, -1, 1, -1, 3, 1, 1, 2 } Returns "IMPOSSIBLE" par { 0, 0, 0, 0, 1, 1, 2, 3, 3, 3, 4, 4, 4, 5, 9, 9, 14, 14, 14, 16, 20 } num { -1, 3, -1, -1, -1, -1, -1, 1, 1, -1, -1, -1, 3, 1, -1, 1, 8, -1, -1, 4, -1, -1 } Returns "POSSIBLE" par { 0, 0, 0, 0, 1, 1, 2, 3, 3, 3, 4, 4, 4, 5, 9, 9, 14, 14, 14, 16, 20 } num { -1, 2, -1, -1, -1, -1, -1, 1, 1, -1, -1, -1, 3, 1, -1, 1, 9, -1, -1, 4, -1, -1 } Returns "IMPOSSIBLE" par { 0, 0, 1, 1 } num { -1, -1, 5, -1, -1 } Returns "POSSIBLE" No cutting necessary.
==========================================================================================
.