PROBLEM LINK:
Setter: Kirill Gulin
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
DIFFICULTY:
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
\begin{equation}
{\textstyle \sum} A_i - x*S >= 0
\end{equation}
For each binary search, we Make a new array T_i = A_i - x thus, reducing the above inequality to
\begin{equation}
{\textstyle \sum}T_i >= 0
\end{equation}
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. ![alt text][16] -
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. ![alt text][17]
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:
-
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. -
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. -
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]
-
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.