PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Hasan Jaddouh
Editorialist: Sidhant Bansal
DIFFICULTY -
Medium
PREREQUISITES -
Dynamic Programming on Trees, Sorting
PROBLEM -
Given a tree with N nodes, select a subset of nodes with minimum sum P[i] and activate them such that they are able to expand to the complete tree. Here by expand for a node u we mean that if at least C[u] of its neighbours are active, then it also becomes active.
QUICK EXPLANATION -
The question is of the format of DP on Trees. For each node we maintain 2 dp’s. Let f(u) store the best answer for the sub-tree of u when we assume that the parent of u will be activated later than u itself. And let g(u) store the best answer for sub-tree of u assuming that the parent of u is activated before we activate u.
EXPLANATION -
The main idea different in this tree DP from other tree DPs is that here node u is NOT dependent on whether its child v is selected or NOT before it, but instead there is a slight difference. Here it is dependent upon whether the child v becomes active (directly / indirectly) before node u itself.
Now there are 2 cases to be calculated when determining f(u) -
Case 1 - u is selected in the answer subset, i.e the cost of this is :
Case 2 - u is not selected in the answer subset. Now here we need to select C[u] children of u which needs to be activated earlier than u, i.e. from which we add f(v) and from the remaining we can add min(f(v), g(v)). Here we can see from the definition of the 2 dp’s that f(u) >= g(u) for every u, this can be seen because in g(u) the node u has the benefit that its parent is already activated.
Now to calculate f(u) in this case, we will sort all the children of u, by f(v) - g(v) and add the f(v) of the first C[u] children and the g(v) of the remaining children. Sorting here works, because the same thing can be seen as this -
First add the g(v) for all children, now add f(v) - g(v) for a subset of size C[u] from the children of u, such that the resultant sum is minimised. Since, \sum_{v = children} g(v) = constant, therefore to minimise this we need to minimise the sum of f(v) - g(v). Hence sorting works.
Similar logic can be extended to calculate g(u). The only difference of g(u) from f(u) is that in case of g(u) the C[u] becomes C[u] - 1 in usage. Note that the answer would be the f(root) of the tree.
Time Complexity - The complexity is O(N * logN) because for each node, we sort its children by their difference of f() - g()
AUTHOR’S AND TESTER’S SOLUTIONS:
AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555