PROBLEM LINK:Author: Praveen Dhinwa DIFFICULTY  PREREQUISITES  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 subtree 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 subtree 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 : $$P[u] + \sum_{v = children} g(v)$$ 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:
This question is marked "community wiki".
asked 01 Jun '17, 23:42

Which node should be taken as root of the tree? answered 02 Jun '17, 12:44

I think this can be solved also in $O(N)$, because we don't really have to sort the values $f(v)g(v)$ of the sons of one node; Instead, we're only interested about the sum of the ksmallest value in that subset, and that can be done in linear time (quickselect, for example). answered 02 Jun '17, 16:23

Could someone explain why \sum_{v = children} g(v) is constant? answered 02 Jun '17, 19:10
