PROBLEM LINK:
Author: Himanshu
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
EXPLANATION:
Consider the input tree as a rooted tree with root at vertex 1 .
This problem can be solved by the following dynamic programming (DP)
- Dp1 , v, k = Vertex v as of the conditions of the following sub-tree problem statement k divided into individual components, vertex v of the vertices of the components, including the minimum value of the sum of the A values of the components including the vertex v when making all the A values positive.
- Dp 2 , v, k = sub-tree below vertex v is divided into k components, and the condition of the problem statement is satisfied except for the component including vertex v of when such a component comprising a minimum value of the sum of the values.
However, when division is not possible, the corresponding DP array value is set to a sufficiently large value inf .
The DP is each vertex v ancillary, such as the following in the DP you will be prompted by performing-
- dp 1 , i, j = A subtree consisting of the i- th child of vertex v is dp 1 , v, k Divided into j components under the same conditions as when the v component comprising a minimum value of the sum.
- dp 2 , i, j As well.
Let’s consider the calculation amount of this DP . Since the number of states is O (N) , and each state update takes the worst O (N) time.
It seems to take O (N3 ) time in total, but if you observe closely, you can see that it works in O (N2) time in total.
The answer is the smallest value of k that satisfies dp 1 , 1 , k \neq inf or dp 2 , 1 , k < 0 minus 1
COMPLEXITY:
O(N2)