You are not logged in. Please login at to post your questions!


CAPTCITI - Editorial




Author: Praveen Dhinwa
Tester: Hasan Jaddouh
Editorialist: Sidhant Bansal


Dynamic Programming on Trees, Sorting


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.


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$.


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 solution: Here
TESTER's solution: Here

This question is marked "community wiki".

asked 01 Jun '17, 23:42

sidhant007's gravatar image

accept rate: 12%

edited 13 Aug '17, 19:46

dpraveen's gravatar image

4★dpraveen ♦♦

Which node should be taken as root of the tree?


answered 02 Jun '17, 12:44

prakhariitd's gravatar image

accept rate: 10%

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 k-smallest value in that subset, and that can be done in linear time (quickselect, for example).


answered 02 Jun '17, 16:23

lukecavabarret's gravatar image

accept rate: 0%

Could someone explain why \sum_{v = children} g(v) is constant?


answered 02 Jun '17, 19:10

thanhkm's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 01 Jun '17, 23:42

question was seen: 1,069 times

last updated: 13 Aug '17, 19:46