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.
==========================================================================================
.
Posting the link to the problem statement would be more than enough. This post is basically 99% problem statement.
HINT: First try to think about in which order the nodes must be processed: if it is possible to cut the tree into several components that satisfy all the conditions there will always be exactly one way to do it which means the components are already formed. You have to find them while making sure all the conditions are satisfied.
Hey,thanks for replying. I couldn't find link to problem statement so, had to copy paste from arena. Sorry for that.
What I am able to think:
if(sum of all positive values != number of nodes)=>impossible
Let numCC=# of nodes with positive values
Then number of cuts required=numCC-1 //each cut increase number of components by 1
I need to divide tree into numCC components such that each component has exactly one node with positive value (say K) and (K-1) other nodes having (-1).
But, this is just explanation of problem statement.
I read a few solutions in arena ,they are using dfs ,but I couldn't understand them fully.
HINT 2: Start with one of the leafs of the tree. What information does the leaf tell you about the component it belongs to for each case (negative or positive)?