×

# CAPTCITI - Editorial

Author: Praveen Dhinwa
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 : $$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:

AUTHOR's solution: Here
TESTER's solution: Here

This question is marked "community wiki".

179819
accept rate: 12%

2.5k52136169

 0 Which node should be taken as root of the tree? answered 02 Jun '17, 12:44 1.1k●2●11 accept rate: 10%
 0 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 1 accept rate: 0%
 0 Could someone explain why \sum_{v = children} g(v) is constant? answered 02 Jun '17, 19:10 0★thanhkm 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,130
×2,505
×765
×102
×58
×9

question asked: 01 Jun '17, 23:42

question was seen: 1,205 times

last updated: 13 Aug '17, 19:46