×

# L56AVG - EDITORIAL

Setter: Kirill Gulin
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

Easy-Medium

# PREREQUISITES:

Binary Search, dynamic programming on trees.

# PROBLEM:

Given a tree with N nodes, a value associated with each node. We are required to find the maximum cost among all possible correct decomposition of tree.

Correct Decomposition of a tree is defined as break down of tree into mutually disjoint set of paths. Path may also consist of a single node.

Cost of a correct Decomposition is given by the minimum among cost of all paths of decomposition, the cost of each path being the average of all values of nodes in given path.

We are just required to find the Maximum cost, not the decomposition.

# QUICK EXPLANATION

• Calculating average and handling comparison of average of two paths with different number of nodes is complicated.
• We can binary search on answer, subtract from initial values the answer and reduce the problem into breaking the tree into paths each with sum>=0.
• Here, We can use dp on tree to check if we can decompose tree into a set of path with all the paths having sum greater or equal to zero.

# EXPLANATION

Reducing Averages to sum of paths

Averages are not good. We can check if average of a set A of size S is greater or equal than x, if

$${\textstyle \sum} A_i - x*S >= 0$$

For each binary search, we Make a new array $T_i = A_i - x$ thus, reducing the above inequality to

$${\textstyle \sum}T_i >= 0$$

Now, it suffices to check if we can decompose the given tree into a set of paths with each path sum >= 0.

Dynamic Programming on Trees

Now, for each value of X, we need to check if decomposition is possible. We have to handle three situations:

• Path starting in sub-tree of node u and moving towards its parent.

• Path starting in sub-tree of node u and ending in sub-tree of node u, such that LCA of start node and end node of path is u.

Now, we have two states for each node - Either node u can be connected to its parent, if required, or not.

So, for each node, we need to maintain two values, let denote $dp[u][0]$ storing path sum such that u is not available, and $dp[u][1]$ such that node u is available.

So, we assume we have solved the problem for all children of Node u and try to solve it for current node. The base case for dp recurrence would be leaf nodes for which both $dp[u][0] = dp[u][1] = T[u]$.

Run a dfs with any arbitrary node as root, and recursively solve the problem for each node, as follows:

Create an empty list and for every Child c, we check if $dp[c][0]<0$, implying we cannot leave this node in this state for a correct decomposition, and add it to the list.

Now, If count denote the size of list, Four cases arise:

1. Size == 0: This means we can even leave the nodes as it is, A likely mistake, when the correct treatment is to connect this node with the child having $dp[u][1] = T[u] + max(0, dp[c1][1])$ and $dp[u][0] = T[u] + max(0, dp[c1][1]) + max(0, dp[c2][1])$, c1 being the child with maximum $dp[c1][1]$ and c2 being the second best child of u, excluding the nodes included in list. For reason behind this, try decomposing following tree for path sum >=0.
4
-5 1 4 2
1 2
2 3
2 4
You'll see that at node 2, all its children have $dp[u][0]>=0$. If we don't connect node 2 with 3, we will have problem getting path sum >=0 for node 1.

2. Size == 1: In this case, $dp[u][1] = T[u] + dp[c][1]$ and $dp[u][0] = T[u] + dp[c][1] + max(0, dp[i][1]), i!=c$, i being child of u, not being in list.
Reason: Now, we have only one child with path sum < 0. We connect it with u and get above values. For $dp[u][0]$ we further connect it with the best child of u, to see if we can make a path of type 2 at node u. $If dp[u][0] >= 0$, it would be left automatically while processing u's parent. Else, it will be added to list.

3. Size == 2: In this case, set $dp[u][1] = MIN$ as we cannot in any valid position, will be able to make node u available for connecting further. Now, the only option is to connect these two child through u and check if path sum >= 0. If $dp[c1][1]+dp[c2][1] + T[u] < 0$, then it is not possible to decompose tree into paths with sum>=0. else $dp[u][0] = T[u] + d[c1][1] + dp[c2][1]$

4. Size > 2: In this case, we cannot decompose tree into paths with path sum >= 0.

Since we can terminate any path at node u, we should set $d[u][0] = max(dp[u][0], dp[u][1]$.

We can maintain a global boolean to check if valid is not set false. Also remember to check that if $dp[root][0] < 0$, decomposition is not valid as type 1 path is not possible and type 2 path give path sum < 0.

Complexity:
Since each DFS take O(N) time, The final time complexity of solution is O(Nlog(max(A) - min(A))), where min(A) and max(A) are the maximum value in given array, the bounds of binary search.

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

3.9k2892
accept rate: 22%

 0 what does it mean when we say u is available or not? answered 28 Jan '18, 14:47 1●1 accept rate: 0% 1 A node in a path may be connected to one or two other nodes. A node is available, when it is connected to 0 or one other node. A node is not available, if it is connected to two other nodes. (28 Jan '18, 21:04)
 0 let denote dp[u][0] storing path sum such that u is not available, and dp[u][1] such that node u is not available. Can someone explain this statement ? answered 28 Jan '18, 17:31 497●1●8 accept rate: 15% 1 A node in a path may be connected to one or two other nodes. A node is available, when it is connected to 0 or one other node. A node is not available, if it is connected to two other nodes. (28 Jan '18, 21:04)
 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,679
×1,672
×1,038
×649
×114
×53
×10

question asked: 24 Jan '18, 20:03

question was seen: 1,895 times

last updated: 25 Jun '18, 02:17