PROBLEM LINK:Setter: Kirill Gulin DIFFICULTY:EasyMedium 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
EXPLANATIONReducing 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:
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:
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: AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 24 Jan '18, 20:03

for those who scared with dp (like me lol !) : Now, just need to find a way to decompose the tree for a given average efficiently i.e. in O(N) ! First finding averages is little tedious so, let's convert it to finding sum i.e. given a particular 'x' we have to find whether the decomposed path has values(averages) <= x. So, intuitively it denotes that each path has the value 'x' and which in turn means that each node in the path has the value 'x' . Now, here is a trick "Every node has a value 'x' atleast So, if we subtract 'x' from each node and then if we sum up the nodes in the path then we must get value >= 0 and that's it ! We have now the problem reduced to : Given a tree with each node a value(val[j]  x), we have to decompose it such that path have sum >= 0 ! (concept of original editorial thanks to @taran_1407) Now, we will focus to solve the reduced problem : For this what we can do? First think that the nodes with values >= 0 are themselves stable (as they can be exist separately). And they have the power to stabilize other nodes. Now, suppose we have something (what is this something..we try to find now) for all the children below the curr_root and we have to stabilize the children (if any one of them is not stable (i.e path sum < 0)). Now, think about how many maximum children you can stabilize? Atmost 2 because stabilizing any one of the child requires that the path has to go to root and it is required that every node is present in exactly one path ! So, at max what you can do take two negative children and merge them with root (if it works then OK otherwise it's simply impossible). So, if more than two children have values < 0 then it's simply impossible. Now, if exactly two children have value less than 0 : we know that in this case we have exactly one possible way out ! If cnt (count of number of negative valued children) == 1 : then we have to take this path and combine it with root and remember we first try to fix it here only (if not possible at all than only we propagate minimal negative value to be handled by upper roots). So, we take the root (val[root] + val[child]) If this sum is itself > 0 then we can see that it can help in stabilizing upper nodes. So, instead of closing the path in the subtree of root we propagate the value to upper levels ! Now, if this is < 0 : can we just pass it to upper level in hope that they will fix it? NO : remember we have to minimize the load for upper levels. So, we first try to fix it in this level itself i.e. in the subtree of the root. For this what is the best possible we can get ? : take another children with maximum positive value. If it fixes the unstable child then OK else we have no chance to fix it here and so, have to propagate to upper levels (in the hope that they will make a try to fix it !) Now final case, cnt == 0 : in this case we don't have to fix any children they are well stabilized and so we can simply pass the value to upper level to help them in stabilizing others ! But wait we are not thinking of the situation when the curr_root is itself negative ! : In this case we have two possibilities : first, combining it with the maximum child will fix it and in this case we simply pass it to upper level for help (as we can't do better than this !). Now, if it won't fix the root : What to do? same approach first try to reduce the load to upper layers and if completely impossible to fix at this level then and only then pass it to upper layers. So, how to fix in this level itself? : we find the second largest child and combine second largest and first largest through root and if it does our work then awesome else just pass the (max_child + val[curr_root]) (minimal value to fix) to upper level in hope that they will fix it ! answered 28 Jan '18, 20:33
sorry forgot to add base cases : For leaf nodes it is just val[curr_node] !
(28 Jan '18, 20:35)
For the first time i have written something please forgive me for my bad english! And if anyone found some counter case then please share !
(28 Jan '18, 20:36)
Link to your AC code with your idea ?
(28 Jan '18, 23:47)
@pk301 "Atmost 2 because stabilizing any one of the child requires that the path has to go to root and it is required that every node is present in exactly one path" I didn't understand this point ? Why atmost 2 ? Or am I missing the definition of path ?
(30 Jan '18, 10:47)
2
A path is defined as the simple path between two vertices u and v. It is understood that in this path, node u and node v will be connected to exactly one other node, and all other nodes are connected to exactly 2 other nodes. Path specifically included by this problem in problem statement is path of length 1, consisting of single node. This way, in no scenario, will a node in a path be connected to more than 2 nodes. So, if more than 2 nodes need to be connected, ans become impossible.
(30 Jan '18, 21:54)
