# 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)

- Dp
_{1 , 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 (N^{3} ) time in total, but if you observe closely, you can see that it works in O (N^{2}) 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(N^{2})