In this blog, sibling dp technique is going to be discussed. But before that, you have to understand what is this technique? where is it used? How to use? Let’s not get overwhelmed just yet. We are going to tackle this subject gradually by discussing a problem.
Let’s discuss this problem. In this problem, we are given a binary tree with n nodes and n-1 weighted edges rooted at 1. We will be given a value q which is the number of edges we can keep/preserve and we will cut/eradicate other edges. Also note that, if we cut an edge, sub-tree forming from that edge will also get cut. Keeping those conditions in mind, we have to preserve q edges where sum of all the edges preserved is maximum possible.
How can we approach that? Well, we can use dynamic programming. Our state will be (current node number, no. of branches still to preserve) which returns a number denoting maximum possible sum of preserved edges. Let’s say we are at node u and we have to preserve m branches. As it is a binary tree, we are denoting two children of u with left_child and right_child and let’s denote cost of the connecting edges to children with left_cost and right_cost respectively. Then, we are going to divide m between two children where each part represents how much edges a child node has to preserve. We can divide m in (m + 1) ways and for each states, we will calculate accordingly and take maximum value among them.
Also remember, if we decide to give a child some edges to preserve, we are of course preserving edge that connects this node to child node. So, we also have to handle that.
dp(u, m) = max(le_cost + ri_cost + dp(left_child, k - 1) + dp( right_child, (m - k) - 1) ), where k = 1 to m-1. dp(u, m) = max(dp(u, m), left_cost + dp(left_child, m - 1) ) dp(u, m) = max(dp(u, m), right_cost + dp( right_child, m - 1) )
Complexity is O(n * q * q) as for each (current node number * no. of branches still to preserve) state, there are q ways to divide among two children.
Now, let’s change the problem a little bit. Instead of a binary tree, a normal tree is given where a node can have more than 2 children. Can we still solve the problem this way? In above problem, splitting a value q in two nodes was quite easy because there are only (q + 1) ways we can do that. But splitting a value q among n nodes will be costly because there are C(n + q, n) ways to do that. So our complexity becomes O(n * q * C(n + q, n)) [C stands for combination]. So, how should we approach this to minimize time complexity?
If we think about this, our 1st problem was easy to solve just because a node had only 2 children. What if we change our tree in a way so that a node only has to divide its resources among 2 nodes and still solve the problem? Well, sibling dp technique to the rescue.
Let’s say, immediate Children of a node are siblings to each other if they are adjacent. That means, a node can have at most two siblings where one is exact left to it and another is exact right to it and they all are children of a particular node. Now, we are going to give each node exact two directed edges. First edge will point from current node to the leftmost children of that node. Second edge will point to the right sibling. Let’s denote them with leftmost_child_node and right_sibling respectively. And that’s it. Our new tree is formed. For better understanding, look at following two images.
Our tree is formed but how can we solve the problem with this new structure? Let’s again say, we are at node u and have m edges to preserve. Now, from u, we can divide m to among leftmost_child_node and right_sibling. But, we have to handle few things. If we give a part of m to leftmost_child, it doesn’t mean we have preserved the edge connecting u to leftmost_child. It just means we have given opportunity to each child nodes to preserve their corresponding edge with u. After that let’s say we have gone to leftmost_node, then u will become parent_node and leftmost_node will become u. From u (previously leftmost_node), we will decide if we are preserving the edge connecting to parent_node (previously node u) or not? If we preserve the edge, we can then again divide m between leftmost_child and right_sibling. Otherwise we will only send m to right_sibling to give other siblings the opportunity to preserve their edge connecting to parent. Here, the catch is that, if we preserve the edge connecting to u and parent_node, then only we will be able to send leftmost_child some edges to preserve.
This is just a problem simple enough to explain sibling dp technique. Lots of problems can be solved with this technique. Whenever you will face situation like this where n resources has to be contributed to many children in a tree, this technique will serve.