DP on Trees : Taking contribution from other subtrees

本站添加: 2026-05-26

[00:00:00]In this video, we will talk about dynamic programming on trees and we will look at a variation which is a bit non-standard.

[00:00:09]In typical DP problem on trees, you might define something like DP of U denotes something that holds for this entire subree of this node. And when you have this definition while computing the DP value of this node you only take the contribution from its children and you can completely figure out what is the DP value of the node that you are currently on just by looking at the DP value of the children.

[00:00:43]So this is the simplest kind of DP problems that are out there. For example, if you want to compute the maximum node in a sub tree, you can use this DP definition. Or if you want to compute the maximum height of a sub tree, you can use this DP definition. Or if you want to compute the sum of all the elements of a sub tree, then you can use this DP definition. And in these kind of DP definitions, you only take contribution from its children.

[00:01:14]But I recently uploaded a video on my YouTube channel that talked about expected values on trees. And there we saw a scenario where for a particular DP of you, it was not sufficient to take the contribution just from the children but you also had to take the contribution from its parent.

[00:01:37]Now this is a bit counterintuitive. How can you take contribution from a parent when you haven't even calculated the DP value of parent yet? So in that video we had seen that you had to split this parent into multiple copies and each copy would represent what are the possible labels that could exist on the parent in the future and that is how you could take the DP contribution from the parent. Now there is also a third class of DP problems that deals with contribution not just from its children not just from its parent but also from its uh siblings. So for this note uh this might take contribution from the siblings sub trees as well.

[00:02:29]This sub tree this sub tree and so on.

[00:02:31]And this technique is usually used in problems that deal with induced subgraphs or spanning subgraphs of a tree. And in this video we will look at another class of problems wherein you are required to take contribution of DP value not just from your children, not just from your parent, not just from your siblings but from all over the tree. that is this particular DP value can take contribution from this node, this node, this node as well as this node.

[00:03:07]So this is a bit chaotic but at the end you'll see that even though it is now taking contribution from all across the nodes in the entire tree the final code would be very simple and although it is a hard problem I would still suggest you to watch the video as long as you can and if things stop making sense you can come back to it later.

[00:03:33]Anyway, with that said, let's start with the problem description. It says that you are given an unrooted tree. So this time the tree is not rooted. So you can't really apply your standard dynamic programming tree tricks. And in one operation you pick whatever the largest leaf is. So here you can see that the leaves are this node one, node two and node three. So you have to pick the leaf with the largest label. And of course the labels are from 1 to n. So there are no duplicate labels.

[00:04:07]So you pick the leaf with the largest label and you color it as green.

[00:04:12]Then with this leaf colored as green, you are now allowed to delete any one of the other leaves which are colored as red. So you can delete this or you can delete this. Now you can see that if you delete one then six will become a new leaf. But if you delete two then four will become a new leaf. In either case once you do the deletion then you have to repeat this process again. That is you again pick the leaf with the largest label. Here you don't have a choice. You have to pick the leaf with the largest label and you have to color it green. If it is already colored green, no worries.

[00:04:53]Otherwise you color it green. And you have to keep on repeating the process.

[00:04:57]But you do have a choice on which other leaf do you want to delete from the tree. So you can see that if you if you start from this leaf three, if you start from this leaf and then if you decide to delete the leaf one, then this leaf six will become the largest leaf. And then from here you you can delete this five.

[00:05:28]You can delete this three. First you'll have to delete this three. Then you'll have to delete this five. But as soon as you delete this five, leaf seven will become the largest leaf because it is also a leaf now. And then the process ends. So in this manner you were never able to color this four in green color.

[00:05:49]But if you were smart about your choices then you could have instead colored it like so. You color you pick the largest leaf which is three but then you delete two first then four will get exposed and now four becomes the largest leaf. So four gets colored green and then you delete three from your uh node and then five gets exposed. So five will become green and let's now delete one then six will become green and so on. So you can see that there are multiple ways to do these operations and in some of the ways the process terminates very quickly and in other operations it might take a while and a lot of might a lot of elements might turn green. So your goal is to find out for each node X which is present in the tree can you color it green in any of the configuration in is there at least one configuration in which this particular node can be colored as green and this is level one of the problem and in case you are interested towards the end of this video we will also talk about level two of this problem where I want to find out in how many of these configurations S can this leaf be colored as green or in other words this is a variation of the code forces problem that appeared in a recent div two round. Uh we want to find out how many unique subsets of green colored elements are there when the process keeps on uh repeating till all the elements are deleted. So how many unique subsets are there? So this part is actually very easy to solve this unique subset part. If you can answer this problem first like for a given node X can you find out if it can actually be deleted from a from these sub tree in these stages when it is colored as green.

[00:07:57]So this is the problem and in this problem we'll see how to take contribution from outside this sub tree.

[00:08:04]Now at this point you might want to stop the video and think about how you would approach this problem. Meanwhile let me also show you some examples of the simulation on how it could go. So you see that on in round one this is the first outcome. In round one, you could decide to delete one from your uh tree and then six will get exposed. Six will become the new maxima.

[00:08:30]Right? So first three was colored as green. Now six is colored as green. And then you delete two. After deletion of two, six is is still the maxima. Six is still colored green. Then you delete three. After deletion of three, six is still the maxima. Six is still colored green. Then you delete four. Even then six is still the maxima. Then you delete five. Even then six is still the maxima.

[00:08:57]And finally once you delete five, seven has become the maxima and the process terminates. So in this configuration you were able to color these three elements in green. But regardless you did have a configuration in which three, six and seven could be colored in green. And another outcome could be that in the first round instead of deleting this one if you deleted two then you would expose four then with four you could delete one and then you would expose six but once you expose six we already saw that the process terminates quickly. And the third outcome is that first you delete this two then you expose four with four you expo you delete this three to expose five with five you expose six and then with six you expose seven and then you are able to color a lot of elements in green. So these are the three possible subsets that are possible. You as you can see that if I ever ask you to find out what are the unique subsets of green elements that you can create, these are the unique sets.

[00:10:07]So these are the unique sets in which all of these elements are colored in green. So in the harder version of this problem, you have to find out the count of these sets as well.

[00:10:20]So now looking at this problem, how do you even think about it? Like there is no way to even begin approaching the problem because first of all the major issue is that the tree is unrooted. You cannot arbitrarily root the tree at node one because this node one itself could be considered as a leaf.

[00:10:46]And then if you root it like so because if you consider this u node five right if you try to root the tree at node five then whatever you are trying to do the definition of a leaf might change right.

[00:11:05]So how do we how do we even proceed right and on top of that not just the uh not just the unordered unrooted tree is the problem the other problem is that once you delete this element the structure of the tree changes very rapidly.

[00:11:25]So how do you act deal with that? So in these kind of problems even though we know that we eventually have to apply DP on trees but the trick is to simplify it down further and further until we can know that we can safely apply DP on trees. So first thing we can do is we can start making observations because you might have seen that in code forces as as and when the problems difficulties increases it's not that it it requires very advanced data structure or algorithm to solve because here you'll see that even though this problem does involve DP on trace but it is not an advanced concept as such. What makes it difficult is some of the key observations that you are missing to simplify the problem. So from the examples that we have seen so far, one thing you can notice that how does the operation look like. So you are picking one element as the pivot.

[00:12:29]You can say that this element is your pivot and using this pivot since this is the largest element largest leaf you are deleting a smaller element. So if a pivot is x it can only delete elements that are strictly less than x. Then looking at this situation alone there is one special element in the tree which is it. So you can see that this node 7 is very special. Why? Because there is nobody in the tree that can actually delete node 7. This means that whatever configurations that you are creating at the end, the last element that is that will enter your set of green colored elements will always be the node 7. Why?

[00:13:24]Because as soon as node 7 gets exposed, as soon as this is exposed as a leaf, as soon as this is exposed as a leaf, then this will of course be the largest label because this is the largest label in the tree. And since this is the largest, then you will have to color it as green. But once you color it as green, then no matter which vortex you delete, you cannot expose a bigger element than it because this was the largest in the tree.

[00:13:57]So with this we can have an idea that we can try to root the tree at this node 7.

[00:14:07]So if we try to root because right now this is an unrooted tree but if we try to root it at node 7 maybe it will unlock some additional info about it because we know that node 7 will be the last to enter the green zone. So this is one observation that we could make. Now what is the second observation? Second observation, you can notice that you are selecting one element as your pivot and you are deleting elements that are less than X. But then after the deletion, if new if no new elements that are greater than X have appeared, then X will continue to be the pivot. And then here you can see that if you pick three as the pivot and then you end up deleting one, then six has appeared as the pivot.

[00:14:59]Then no matter what you delete, as long as seven does not appear, six will remain the boss, six will remain the pivot and everybody smaller than six will be deleted. This means that the elements turn green in increasing order.

[00:15:15]So you see that first three turned green, then four turned green, then six, then seven.

[00:15:22]So this is something obvious, but also something very easy to miss. So these are the kind of observations that you have to make to simplify the problem. So we have made two observations so far.

[00:15:34]One is that the node 7 is the most powerful node because nobody can delete it from the tree because once it starts acting as the pivot then it will delete every node and it will not let any node become green. It will remain green forever. So this means it will be the last element to enter your set of green elements. This is the first observation.

[00:16:01]And the second observation is that the deletion happens in increasing order.

[00:16:06]And this is fairly obvious because once you pick node X as your pivot, then it it will remain maximum element as long as you delete something which exposes element that is X plus delta.

[00:16:22]So with these two observations let's formalize it. You can see that elements turn green in increasing order. We have already seen this and we are we have seen that there is one special element which is the largest element and the largest element will always turn green.

[00:16:40]Nobody has the power to delete it and nobody can actually turn green after it because of the observation one because since elements enter in increasing order. Then once seven has turned green then after seven nobody can turn green.

[00:16:59]Now how do we utilize this fact? So since this n is very special, let us try to root the tree at this node which is the highest node of this tree and maybe this will unlock something. So I have rooted the tree at the highest node which is 16. Now remember that I told you earlier that problems on code forces they are difficult not because of advanced algos but because of some observations that you have to make. Now if you have already made these two observation that is elements enter in increasing order and you and node 7 is is special so you can actually root the tree at this node then the problem difficulty has reduced drastically.

[00:17:53]So I believe at from this point onwards this is hardly a diff to let's say diff to D.

[00:18:02]Previously it was a diff to E but now it's a diff to D after making these observations. So now that we have rooted the tree at node N what can we see now? Notice that it creates several branches.

[00:18:22]This is the highest node and of course you will start your operation at the node 11. This is the first node that you would start your operation at because this is the highest leaf that is present. Right now if I ask asked you okay looking at this tree tell me which nodes can actually turn green and which nodes can can never turn green. So this is a difficult problem to solve. But looking at this thing, you can say for sure certain elements that will never ever turn green.

[00:19:02]Which are those? So first of all, all the leaves except 11, these will never turn green.

[00:19:10]So let us mark it as red because 11 was chosen as the highest leaf. So these can never turn into green right? Uh let me do something like this.

[00:19:26]These can never turn into green.

[00:19:32]Now is there any other node that could that can never turn green? So let's look at this node four. Can this node four ever turn green?

[00:19:46]The answer is no. Why is that so?

[00:19:49]Because for node four to be turned green. So if four wants to be turned green, if four wants to be green, then first of all it has to be a leaf vortex.

[00:20:06]But if it has to be a leaf vortex then three has to be deleted. Six has to be deleted. I mean but who can delete six?

[00:20:14]We know that X can delete anything that is smaller than X. So this means six can be evicted from the tree only by an element that is greater than six.

[00:20:29]And then once six is out of the game, four will enter the game as the leaf node. But whoever had the power to delete six from the tree, do they not have the power to also delete four from the tree?

[00:20:44]So it's obvious that if six is never winning, four is also never winning. So four does not have a winning chance at all. So right now you are not sure which elements can be converted into leaves or not. But you are sure for certain elements that they can never ever be converted and one such element is four.

[00:21:07]What about 10? So you can see that 10 is also such an element. Why? Because for tent to turn green, it has to be exposed as a leaf.

[00:21:20]But if it is exposed as a leaf, then all of its neighbor must die first. But one of its neighbor is 11. Who can actually kill 11? Something that is greater than 11. But if something that is greater than 11, suppose it is 13. If 13 has the power of killing 11, why doesn't it have the power of killing 10 as one? So this means that this 10 also never stands a chance of becoming a leaf vortex or becoming a green vortex I would I should say.

[00:21:56]So with this let's see what the possible candidates could look like. So assume that the game has not started that is I have not started the game at node 11. I could start the game at any leaf vertex.

[00:22:12]But no matter where you start the game, right? No matter where you start the game, you can see that this 10 can never ever be a candidate.

[00:22:24]Similarly, this four can never ever be a candidate. And why is that? Because this has so this node X it can never be a candidate when in its sub tree. You can already see that we are heading into dynamic programming territory.

[00:22:45]So if this node is let's say 10 then if any node in its sub tree is greater than 10 for example if that node is 13 then for 10 to become a leaf node only then it could be colored green 13 has to be deleted not just 13 the entire subree has to be deleted but 13 is part of the sub tree but whoever can delete 13 it means they are still around but if they are not around something even more powerful than it is around because we said that nodes enter the green set in increasing order. So every time a new element arrives it is more powerful than the last element that you had seen.

[00:23:32]So this means that if you look at uh a general tree and suppose this node is let's say 23 then this node is a candidate or you can say that this node will never ever enter the green set if and only if there is one element let's say this element if this element is let's say 27.

[00:24:05]Then you can see that when the process reaches over here somebody must have deleted 27 and that somebody is still around it means that they will also delete 23 or somebody more powerful is there it means that 23 can never get a chance to become the leaf green leaf vortex that is become the leaf with the maximum value.

[00:24:31]So you can see that if you define something like this, if you define a DP called max below.

[00:24:46]So max below of U would represent that for this particular node U.

[00:24:54]What is the maximum node in this sub tree that is below it? This sub tree.

[00:25:02]Similarly for this node it would represent what is the maximum node value in this sub tree.

[00:25:15]So this is the definition of max below of u. So now you can see that you can since this is a rooted tree and you have defined max below of u as the maximum node value or the maximum node label in this rooted tree then you can simply apply dp on trees where you simply take contribution from its children. So what will the dp transitions look like? It would be dp of u is equal to max of dp of child comma child since we want the maximum level. So DP value of this would represent maximum in this entire sub tree excluding this. DP value of this would represent maximum in the entire sub tree excluding this. And DP of this represents maximum in the entire subree excluding this. But the DP value of this should represent maximum in the entire sub tree excluding this.

[00:26:25]This means that you compute the exclusion of the children and then you add the children back. So that's why dp of u would be the maximum of dp of child comma child. So this is just the maximum sub tree uh dp but here we are not counting the counting the node u itself. So that's why the dp definition is max below.

[00:26:52]Right? It's not I'm not talking about the maximum value of u on the uh sub tree. I'm talking about the maximum value below the sub tree. Now I could have also defined it as maximum value of U inside this sub tree including this node and you could claim that if this is node 23 then you could claim that if you had this DP definition it would make things simpler and the DP transitions would also be simpler that max of U denotes the maximum of this entire subree including this node and then you can simply check If max of U is not equal to U, then you can claim that this node will never be a green node. And this also works. I'm not saying that this will not work. But I am specifically I'm specifically uh adding this DP definition where I do not count this node as part of your DP. Why I'm doing that? That will become clear later when we do some more observation when we want to find out the actual feasibility check. But for now this is what your DP this is what your max below represents.

[00:28:14]So now that we have this DP definition you can see that we are just making couple of observations and we are saying that okay these are the elements that will definitely not be in your final set. Right? We said that 10 will definitely not be in your final set.

[00:28:31]Four will definitely not be in your final set. But we haven't really made any real progress as to solving the problem. How do you actually guarantee something that will not be your in your final set or will be in your final set?

[00:28:47]Because as you can see that uh if this element suppose if there if this element is 22 and there is nothing that is uh bigger than 22 over here. Can you actually guarantee that this element will be in your final set? You cannot guarantee that. Why? Because let's say this element is 25. Then you can already see that other sub trees are now affecting this element and just being your sub tree maxima is not enough for you. There are other conditions that you might have to satisfy for you to remain in the final green set.

[00:29:31]So what are the conditions? Let's see.

[00:29:34]Suppose if I fix this element and I ask you can you make this element X. Suppose the node level over here is X and I ask you can you turn it to green? So can this node be turned to green?

[00:29:53]Then of course you started your game at some particular node. Suppose this node is suppose this node is S which is the starting point.

[00:30:07]Then if your goal is to turn this green you can see that you can apply a greedy strategy. You can make an observation that you can apply a greedy strategy.

[00:30:21]And what do we mean by a greedy strategy? The grad strategy says that if you want to make this element as green then you should not touch this node or this node or this node or this node or this node etc. Why? Because if you touch it, if you delete these note from your tree, then this could only expose bigger element and as then when the elements become bigger, this has less and less chances of becoming the maxima. So if your goal is for is for this to become the maxima, why do you even want to touch the other elements that are not on its path? So you you fix this as your pivot and you start deleting this node.

[00:31:13]You delete this. You delete this. And of course we are assuming that this s is less than this x. Right? Because if this itself is uh bigger if s is bigger than x then of course s will simply delete it instead of letting it be the maximum.

[00:31:34]So we assume that okay you delete this you delete this and you delete this. But now you can run into some problem. Now you can see that suppose after you are dealing doing these deletions this element becomes s+ one. So now your goal was to not touch any of these elements on the right hand side. But now once your pivot lands over here in this sub tree, you are actually forced to touch the other elements.

[00:32:06]But now you can see that your greedy strategy will no longer work. Because if this is a pivot x s + one, let's say this number is 27, then if you have 12 over here and if you have 9 over here, then of course you have to delete something from the other sub tree because you have to move the pivot from this sub tree to some other subree.

[00:32:29]Otherwise, if you do not move the pivot, this will never be exposed as a leaf.

[00:32:35]Because for this to be exposed as a leaf all of its children must be deleted. Not just the children but the entire sub tree. But for the deletion to happen a pivot must exist and the pivot has to be outside this sub tree. So then if you have this 27 do you just go ahead and delete this 9? No. That is very risky but because an infinity could be hiding over here because after you delete this 9 and this 12 infinity could emerge and then infinity would take over and it will never let x become the winner. It will never let x become the largest value.

[00:33:16]So then if greedy strategy does not work what do you do?

[00:33:21]And suppose if even if it did right suppose if this is s + one and uh let's say that you want to let's say you want to figure out for this node let's say you want to figure out if you can turn this to green or not and suppose this element is your current pivot.

[00:33:46]This element is your current pivot.

[00:33:50]Then you first of all you have to move this pivot to some other sub tree and you have to do that smartly right so that you don't expose a very big element. So first of all the strategy is not clear which sub tree should we move this pivot to but assume that you are able to move this pivot over here. This is the new pivot. Then what could happen is that you can keep on doing the operation and then again the pivot could land back over here. This could again become the new pivot and then you have to move it to some other sub tree. Let's say you move it over here. But then this after this does some deletion this becomes the new maxima. Then you have to keep on doing this. So now you can see that it is getting very complicated because the pivots that you have it can keep alternating right. Sometimes it can be in this sub tree and then it can come back here and then here and then here and so on.

[00:34:45]So again you have to make some observations that can avoid dealing with so many pivots.

[00:34:54]So try to pause this video and think of one such pivot that will help you simplify things.

[00:35:06]So if you notice that this is the observation and this is not trivial to see that if this is your node X that you want to turn green then instead of focusing on all possible pivots in this subtree that could become pivots at any point of time why don't we just focus on the last pivot That is why don't we focus on the last element in this sub tree that could realistically become a leaf node. We are not saying that it will guaranteed to become a leaf node a green node but that has some chances.

[00:35:52]So the last pivot which one could it be?

[00:35:56]If this node is X, we already know that whoever who wins the battle in this section that is nothing but this quantity that we had computed with DP before which was the max below.

[00:36:18]So max below of x would mean suppose the maximum value that is smaller sorry the maximum value in this subtree excluding x that is in this lower subay is located over here. Suppose this is the maximum value. Let me color it color it as blue.

[00:36:37]This is the maximum value.

[00:36:41]Then pivots can keep on alternating left and right. We don't care. But at some point of time the at some point of time this will be exposed as a leaf node. Since you are since you are deleting everything then at some point of time this will be exposed as a leaf node.

[00:37:03]Now since this is the maximum since this is the maximum in the circle that I have drawn in the red circle that you see this is the maximum that I have drawn it means that whoever deletes this they will also delete this they will also delete this they will also delete this and this time the grid strategy would work because this time the pivot won't change anymore so suppose This node let's say this node we are dealing with suppose this node is the pivot this is your pivot that ends up deleting this node right that ends up deleting this node and of course this pivot has to be greater than this of course then it will delete it then you can see that you don't actually have to touch these sub trees at all because they could expose bigger elements which would make it very difficult for X to become the maxima. So if this is the pivot, it will delete this, it will delete this, it will delete this, it will delete this and then it will arrive at a situation where this is exposed as a leaf and this is exposed as a leaf. So now the only competition is between this X and the element that was used as the pivot.

[00:38:29]So now you can see that when the process finally reaches this, when the process finally reaches X, if this is X, when the process finally reaches X and X has become a leaf node, that is all the elements in this red circle are gone.

[00:39:00]All the elements in this red circle have been deleted.

[00:39:05]Then what are the possible pivots that could exist?

[00:39:14]So you can see that since the maximum value of this red circle has been deleted and this maximum value was nothing but let's call this as L max below of X. Let's define it as X. So since the maximum value of this red circle has been deleted then there there could be multiple different leaves that could have deleted this.

[00:39:44]But the possible pivots that are now existing, that is the possible leaf nodes that are now coexisting with X, they would have to be strictly greater than X.

[00:40:00]They would have to be strictly greater than L.

[00:40:04]Right?

[00:40:08]So now let's locate all the numbers that are strictly greater than L.

[00:40:14]in this tree and suppose this x value is 7 and L value is 2 or let's say L value is three. Now you can see that if there is a leaf so all the leaves that will be exposed the maximum value of these leaves will of course have to be strictly greater than three because it deleted three. So it has to be four 5 6 7 8 9 10 etc. So if we can if we can create an environment wherein the maximum exposed leaf is four or five or six then we are good because if if these were the pivots that were used to delete this entire circle then we can say that once this entire circle has been deleted this will become become your new pivot because this will become the new maxima as long as you ensure that this pivot that you used is strictly less than your your strictly less than the value that you are at currently. So assume that L is equal to three. So let us locate where four is. Suppose four is available over here. Five is available over here.

[00:41:46]Uh let's say six is available over here.

[00:41:49]and yeah four five and six.

[00:41:56]So what do you need? So you can see that if you want this element to turn green then you need to find out if this element can turn green because if this element can turn green then it means that there is a world in which this element is the leaf node and is the maxima. So you can use this as your pivot and then your pivots will not alternate anymore. And the greedy strategy that we had discussed will work because if there is indeed a world in which this element can be converted to a leaf then you can lock down this leaf and then you can keep on deleting this deleting this and you can keep on deleting the entire thing and then you can expose this and this in a competition and then this would win.

[00:42:50]Similarly, if you can find out if there is a world in which this five can be exposed as the maximum leaf, that is if this five can become the maximum leaf that is available. This means that there is there is some way for you to delete all of these leaf vertices and expose five as the maximum leaf. In that case you can lock down this five and use it greedily to delete this entire thing.

[00:43:22]And you can do that you can delete you can actually delete this entire thing because this five is greater than this max below right max below means the maximum element in this sub tree which was required to clear this entire sub tree so that this becomes a leaf element. So we can actually do that. So now you can see that the DP value or in fact let's actually now define the DP definition what do we want? So notice that right now it is actually not possible to figure out whether it is whether whether it is actually possible to convert this four 5 6 or seven as the leaf nodes maximum leaf nodes. Right?

[00:44:02]But we are saying that if it is indeed possible then if the answer to this is yes then the answer to this is also yes.

[00:44:11]So you can already see that the answer to this node depends on the answer to this node which is in a different subree depends on the answer to this node which is in a different sub tree depends on the answer to this node and so on. So we define a simple debate definition. We say that okay DP of I is true if it can be colored green. This this is the most simple DP definition can that can you come up with only the transitions are non-trivial that is you want DP of I to be the maximum leaf in all of the leaves that are exposed at that point of time.

[00:44:48]So this is the DP definition.

[00:44:51]But then how do you populate this DP of I then you can see that with the reasoning that we have discovered this D for populating DP of let's say R suppose you want to populate DPU of R let's call this node as R then first you find out a quantity called max below that is the what is the maximum label in the sub tree because you would need to clear that label from that sub tree so that this turns into a leaf. It means if the maximum label is 9 then you need a node which is more powerful than 9 which is greater than 9 which can delete this. So you define max below of R you say that this is your max below of R which is 9.

[00:45:49]Now you don't know uh now now the next thing that you do is that if this is your L you know that you need something that is strictly greater than L somewhere to be exposed as the leaf this means that you want their DP value of strictly greater than L to be greater than so so let's say DP of L + 1 so if DP of L + 1 is indeed true then it will indeed be possible to clear out this entire sub tree right so first we do first what we'll do is with this L let us locate all the occurrences of L and all the numbers from L to R that is if this is L and this is R like let's say uh let's say L is 5 and R is 10 or R is 9.

[00:46:51]Then if uh this is like let's say L which is five then you locate where six is you locate where 7 is you locate where 8 is and you yeah you just locate 6 7 and 8. Then you can see that DP of R would be nothing but DP of 6 or DP of 7 or DP of 8.

[00:47:29]This means what does DP of 6 represent?

[00:47:33]DP of six represent that there is a configuration. Look at your DP definition. DP of six means there is a configuration in which six is the maximum leaf standing that is six is the maximum exposed leaf. So using this six as your pivot you can clear clear out this entire sub tree and once this has been cleared out since nobody else was competing with six beforehand since six was the maximum leaf extending then only you are in competition and since you are nine then you will win the battle and you will become green.

[00:48:09]Same for seven. If you can expose seven in the maximum leaf then with this fixed pivot you can delete this entire sub tree and eventually seven and 9 computes and nine bends. Similarly with this eight.

[00:48:25]So you can see that dp of r only depend only depends upon dp of l and l is of course strictly less than r.

[00:48:39]So even though these values could be scattered all around the tree, you can see that they are part of the different subree. One is part of six is here, seven is here, 8 is here, 9 is here. Now this requires some sharp observation skills to notice that even though these values are distributed if you populate your DP in a smart order and that smart order is that you populate it from left to right then by the time you want to compute the DP value of like let's say R is equal to 25 you will have already computed the DP value of all of the smaller uh nodes and for computing the DP DP value of R. You only need the DP value of L.

[00:49:30]This is L. Like let's say L is L is like let's say 17. It means that the maximum label in this sub tree is 17. So you just need this 7 from 17 to 25. You need is there any configuration in the world where one of these leaves is the maximum leaf? Because if that if such a configuration exist then I can use that to delete my entire sub tree and then I can become the leader.

[00:50:02]So with this you can notice that since DPR only depends upon on the values on its left hand side if you just populate DP from left to right it will simply keep on taking contribution from all across the sub tree and you don't actually have to do the traversal at all.

[00:50:22]And that's it. That with that you will be able to compute the DP value and you are able to solve the problem.

[00:50:31]So it still kind of feels like magic, right? Because you defined a DP definition, it worked. You looked at the transition, you figured out the order in which you want to populate. But uh some of it still feels like magic like how how is it how is it actually covering all the cases and how does just computing the simple max blow DP take care of all the cases. So that's a bit uh I mean difficult to teach you the intuition for I would ask you to take some cases and try to draw it on paper and see why why if you want to compute the DP value of 23 and even if all these smaller nodes then 23 are scattered all across over here over here over here over here and over here why populating the DP in increasing ing order actually corrects actually fills the correct DP value in all of them. So I mean it's not obvious that but part I will agree it's not obvious to think of that but uh but still it's it's a good exercise for you to see uh why just populating now at least I hope that uh the transitions are clear right like because we know that if you want this 23 to become the maxima then whatever is the maxima here they need to be deleted and if they need to be deleted they need to be deleted ed by a pivot outside and if they need to be deleted by a pivot outside then you need to have a world where this pivot is the maximal green element. This means that this is nothing but the DP value of that pivot and if that pivot exist find out all such pivots and we don't care about the pivots that are greater than 23 because they will delete 23 as well. We want 23 to lead. So we want 23 and if this is 17 we want a pivot that is in between so that we can use that pivot to greedily delete this thing and then we will become the maxima.

[00:52:39]So you see that this is more of an observation based problem rather than DP but then most of the DP on tree problems are like this only. It's not like you have to apply very it's not like that there are a lot of complicated DP tricks for trees. Okay, there they are very limited and in most of these problem you'll have to do and notice these observation and you'll have to realize that greedy strategy does work that if your pivot is fixed it is a good idea to only expose only delete these elements do not expose any other things but then you are forced to change the pivot back and forth but then if you focus on the maximum element in this sub tree that is why we had defined it as max below and not as max in this sub tree. So if you just focus on this max in this sub tree which is the max below then if you look for the pivot for this then if you start from that pivot if you convert your tree into a state where you start from this pivot then your pivots will no longer alternate and then this will become the maximum.

[00:53:50]So let's look at the DP definition and transition. So first of all you have to do normal DPON trees where you compute the uh where you do a DFS uh let's say so this is your standard DP on trace and here you see that you want to compute the max below of this. So this would be nothing but max below of this max below of this max below of this comma the value of this right value of each of the cell. So this is a very simple O of DP. So this is how you apply DP on trees. So remember at the start of this video we told you that this problem is DP on trees but how and where to apply that DP on tree that was the challenging part. So this is one aspect where you are able to apply DP on trees.

[00:54:46]Now the second thing is that we have to apply the normal DP where you for a particular node like let's say for this particular node.

[00:55:11]So first of all you want to find out the DP value and you know that the root this is the root root will always be turned green right that we know for sure because eventually it will be turned green so the DP value of root is always true and what is the other element that is is special the other special element is the largest leaf that is where the process starts suppose this is the largest leaf then it will always be turned green that is for This is the largest leaf.

[00:55:52]Okay. So, this is the largest leaf and then Okay. Okay. I think I jumped something.

[00:55:59]So, yeah. So, the root will uh root will always be colored green and the largest leaf will always be colored green. And then you iterate over all the DP values in increasing order right you you iterate in increasing order and you you take the contribution from all across the trees without even realizing it. So you first compute what is the maximum label in your subree. This is your this is the maximum label in your sub tree.

[00:56:33]And then you find out if this maximum label is L and the value that you are on is that R then you find out if the pivot that you used can you is there a pivot that you can use that is greater than L but smaller than R. So then you iterate over this entire range and you see if any value is true in this range. So you can say that this DP by itself is O of N².

[00:57:04]Why? Because for each R you are finding the minimum below and then you are iterating over that range.

[00:57:12]So how do you convert it to O of N? This is a very simple optimization that you can do because if you represent this boolean as zeros and ones, if this is your DP array, so you can notice that you are computing this DP array. This is 0 1 2 3 4 5 6 7 8. for this uh DP of five your max below will of course be strictly strictly less than five. It could be this as L. And then you want to see if there is a pivot in this range. This means that in this range is any of the DP value true. So if you set the false DP value as zero and the true true true DP value as one then you are you just want to know is the subarray sum over here is it strictly greater than zero or not. And since you are always looking for a subarray sum and you are always appending then you can construct the prefix sum array in an online fashion and with this prefix sum array you can simply query the subarray sum in O of one. And why do you not need segment or any other fancy data structure? Because segmentry or fancy data structure is needed when you want to go from left to right but you want to update elements that you have already seen so far. But this time you are not doing that. This time you are only updating DP of R and then you keep on moving right. So prefix some array can actually be computed in an online fashion which is what I have did over here. This is see for understanding DP on trees just this implementing this O of N square idea is good enough. Like if you understand why this O of N square DP on tree idea works for just checking the feasibility that is good enough. But if you want to optimize it, you can see that you you define a prefix some array that counts the uh subarray sum that gets the subarray sum in O of one and then all you have to do is query the subarray sum and you have to check if the sub subarray sum is strictly greater than zero or not.

[00:59:28]So this works and this kind of concludes the first part of this video where we wanted to check the physibility that is can any node be colored green in any of the configuration or not right and and we just and we saw various techniques to solve this. First is the greedy idea.

[00:59:47]Then we made some observation. We read we we rooted the tree at this node. And then we said that uh uh we have to define a sub tree DP which is very simple and you have to compute the maximum that is below the sub tree and then you you focus only on that node and then you focus on the pivot on the other sub tree that will delete this node. If it deletes this node, it deletes this entire sub tree. Then this and these two compete and then this wins and then you compute the DP value of this and so on.

[01:00:22]And then we finally saw that this DP computation can actually be done in increasing order of the labels and that actually takes care of taking contribution from all across the sub tree which is a technique which you might not have seen before in sub trees.

[01:00:38]And finally we saw some DP optimization where we saw that every DP value R is only taking contribution from a range from its left hand side. So we could use prefix sum to compute the subarray sum efficiently.

[01:00:54]So all that is fine for the first part of this video. Now for the next part of this video you can skip it if that's already too much information for you. So the next part of the video talks about this case that uh if you keep on doing these operations until no more elements are remaining.

[01:01:13]What is the number of unique subsets that you can create? So you can see that I keep on saying subset but I I actually mean sets. So what is the number of unique sets that you can create? So this is one set like first you delete first you take three in your set first you color three as green because this is one of the maxima then you color six then you color seven then this is another configuration this is another configuration so and in this tree you can see that there are only three other uh only three configurations. So you have to find out how many unique sets you can create while doing this deletion process. So try to pause this video and think about the solution. This solution is actually very trivial if you have actually understood the greedy strategy of taking a pivot and then deleting this. So take a minute to pause this video and think about the solution.

[01:02:09]So you have to find out how many unique sets are there. So how do we solve this version of this problem? So this is same logic as before. You can notice that what you delete does not matter.

[01:02:22]Instead, what you keep that only matters. That is what is the pivot that you are keeping. So the first pivot that you kept is three. Second pivot that you kept is six. But you notice that once you keep a pivot of six, you cannot introduce any element that is smaller than six. So pivots enter the set in increasing order.

[01:02:45]So if that is the case, how do you find out the number of uh unique subsets?

[01:02:52]Now notice one thing that in all of these subsets, the last element will always be the root node which is the root node which is seven. So if you want to compute the number of subsets, right?

[01:03:08]If you want to compute the number of subsets, let's define something as this. DP of I previously we defined as DP of I is the is true if it is possible to be colored green. Now notice that when you enter the set right when you enter the set what matters is how many elements have already gone in before you entered the set. So suppose the process uh right now the process ended at the last node of the tree which is node 7 right then here we are saying that suppose the process will end when the node I enters the set. So tell me how many ways are there for node I to enter the set. So if node I is entering the set, it will of course be act as the pivot at that point of time because only the pivots get added to the set. So suppose you want to compute the DP value of this node. This node is X and you want to find out in how many sets you want to end the game basically you want to end the game when this element lands into the set. So tell me tell me how many sets can you actually create where X is the last element of the set.

[01:04:32]And if you can do that then your answer would be DP of N because by definition how many sets can you create where the last element of your set is equal to N.

[01:04:44]And this is nothing but our answer because our game continues until the last element has also been added. But this time we are adding a variation. We are saying that okay I want my game to end when the last element that has been added to my set is X. So can you compute how many ways how many unique sub how many unique sets I can create such that the last element of my set is equal to X.

[01:05:12]So again you can use that same strategy that if X has to enter this set let's look at the sub tree that is below it and let's look at the most important element in that sub tree that element is nothing but the max below right this is the max below let's look at this max below of X now if this is your L then If this element needs to enter the set, there has to exist some pivot that is strictly greater than L but less than X. Right? So in fact, let me write it as R. That would be easier to reason about. So this is R and we want to find out max below of R. So let's locate where these numbers are present. So suppose this is L + 1. This is L +2. This is L + 3. This is L + 4.

[01:06:16]This is L + 5. This is uh L + 6.

[01:06:22]Then this time you want to know that okay if you are entering this set then what is the what is the element that has entered right before you? What is the second last pivot? because we know that we want to end the game when X enters the set. So this time we want to find out okay what are the possible choices for the second last pivot. Of course the second last pivot has to be strictly greater than L because it has to delete this L since R wants to enter. So this sub tree has to go right and then of course it has to be strictly less than R because R and that pivot will compete and R will want to enter the set. So this means this DP of R if you can find out the number of ways in which this element is the last element to enter then you can create a new set where these two elements are the last consecutive pairs or if you can find out the number of ways in which this element is the last element to enter then you can append these two to create a unique sets. So this means that DP of R is nothing but summation of DP of L + 1 to R - 1. That's all.

[01:08:00]So this same trick as before but instead of just maintaining boolean we now maintain number of ways in which this element is the last element that is entering the set. Then what is your starting condition of the DP? So suppose this is your maximum starting point.

[01:08:20]Then DP of S is equal to 1 because there is only one set in the world where this element enters as the last element. This is the only element and then you expand this set. How do you expand it? you try to find out okay for DP of S + one or like let's say for DP of S + 5 then you want to find out how in how many ways can DP of S + 5 enter the set then you simply find out in how many ways DP of S+ 4 can enter the set and since the ordering is fixed then it has to enter S+ 5 has has to enter after S+ 4. So with this you can compute the total number of ways to enter as the last element and the code is exactly the same as before.

[01:09:15]So this is the code that is for starting value of your DP is the starting the maximum leaf is one and otherwise your DP value is the summation of DP values of all the elements that are smaller than U. but greater than your uh max below because you want these are the elements that can act as your pivot on the other sub trees while you compete with them and you become the next pivot and then of course this can be optimized to O of N and this solves the problem almost. There is one minor thing that is remaining and this minor thing you can try to pause this video and think on on your own but otherwise whatever you see on this code whatever code you see on this screen is 100% correct and this actually properly computes the DP value of all the things except one things for which it doesn't in it doesn't compute incorrectly but it doesn't actually compute anything because if you look at this loop loop it says r is equal to0 r less than n and it says max below of r.

[01:10:28]So what happens to the root? So if this is the the root what is the max below of root? So max below of root will always be n minus one.

[01:10:38]Right? So max below of this root will always be n minus one. But then you are iterating over n minus one + 1 which is n and n is not strictly less than n. So DP of N is actually never ever populated. I am not saying that it is populated incorrectly and we have to fix it later. It is actually not even computed. So this code is correct and it can give you the total number of ways in which the last element to enter the tree is 1 2 3 4 5 6 7 8 9 10 etc. except it cannot give you the total number of ways where the last element to enter the set is 16. So this is another observation based uh section of this video that you will have to find out on yourself that is how do you compute the number of ways in which 16 is the last element to enter if you already know how many ways are there where 15 is the last element to enter 14 is the last element to enter and so on.

[01:11:43]So how do you do that? So try to pause this video and think of a solution.

[01:11:54]Okay. So let's talk about the solution.

[01:11:59]Now this DP of N, I want to compute this DP of N because it is not being computed by this DP formula that I have shown on this screen. Right?

[01:12:14]Now when n enters the set all right when n enters the set when can n actually enter the set? So you see that there are several branches. So this is one branch.

[01:12:32]Basically each child creates a branch.

[01:12:34]This is the second branch. This is the third branch. This is the fourth branch.

[01:12:41]And this is the fifth branch.

[01:12:46]So if n wants to enter the set then all branches except one all branches except one needs to be deleted.

[01:13:01]Right? All branches except one needs to be deleted so that this becomes the leaf. Why is that so? Because Because if you look at the degree of this node right now it is what it is connected to 1 2 3 4 5 no 1 2 3 4 5 it right now has five child so it its degree is five but if four of its children gets gets deleted then its degree will become one and then once it gets exposed as the leaf node nobody can stop it from entering the set as the maxima.

[01:13:52]But think about it if all of these children needs to be deleted so that it becomes exposed as a leaf node then this entire subree needs to be deleted.

[01:14:06]This entire sub tree needs to be deleted. This entire sub tree needs to be deleted, right?

[01:14:14]And only one sub tree must remain.

[01:14:19]So without loss of generality, let's assume that this is the sub tree that is remaining.

[01:14:28]This child is remaining.

[01:14:31]This means that one of these nodes has the power to delete. Suppose this node is X. One of this node has the power to delete this entire thing. This entire thing, this entire thing and this entire thing.

[01:14:50]Why? Because if this does not have the power, then maybe this node has the power or this node has the power.

[01:14:57]Otherwise if it does not has the power to delete this then we switch to this because then that is the leading node right.

[01:15:07]So assume that this node has the power to delete this all the all the other elements from all the other sub trees.

[01:15:16]Right?

[01:15:19]We are saying that one of these note from here it has the power to delete everything from all the other sub trees. Right?

[01:15:34]Now think about it like sure this is node n but then if you if you ignore n does any node has power to delete all the other nodes like so many nodes like which node has so much power if you think about it there is only one node that can have so much power which is n minus one and by the way uh this heading says dp n minus one but this I mean zerobased indexing But in my visuals, I'm showing a one based indexing.

[01:16:08]So think about this node n minus one.

[01:16:12]Now nobody actually has the power to delete node n minus one, right? Nobody has the power to delete node n minus one. So let's locate where node n minus one is present.

[01:16:25]Right? Suppose this is node n and suppose node n minus one is present over here.

[01:16:35]Then you can see that we said that in order for n to be exposed as a leaf only one branch must remain and one of these nodes pivots it is so powerful that it can delete all of these other branches.

[01:16:55]But is there actually anybody in this area or in this area or in this area that is powerful enough to delete n minus one?

[01:17:04]So you can see that nobody is powerful enough to delete n minus one. So nobody can actually expose n minus one as a leaf node except somebody from this area itself.

[01:17:19]So now you can see that where n minus one is located in the tree that becomes very relevant.

[01:17:30]So assume that n minus one is hiding over here. This is your location for n minus one and this is n.

[01:17:46]But then does it mean that? So sure only only one of the pivots from this chain this branch can delete everything right and what is that element that can delete everything? That element is n minus one.

[01:18:05]But does it mean that we actually have to delete this and we have to peel off this? We have to peel off this this and this and this and then we have to arrive at n minus one as the pivot to actually delete all this entire thing.

[01:18:22]So if you think about it it is not we it is not compulsory for us to wait for n minus one to delete everything because what if this pivot over here what if we expose this and this pivot is x.

[01:18:39]So if this pivot is X, what if this alone is powerful enough to delete this, this, this, this, and this entire thing.

[01:18:48]So when can that be possible? Because if that can be possible, then you can see that N doesn't always have to enter the set set after N minus one. It can actually enter the set after X itself.

[01:19:04]Why? Because N minus one is hiding above N minus one. So it is shielded. It is not a leaf node yet. And then n can enter the set after x and then after that nobody can remove n.

[01:19:18]So what is the property that x should hold such that it can actually delete all the other branches because it doesn't have to delete elements from its own branch.

[01:19:30]It only has to delete all the other branch.

[01:19:35]So let's locate where n minus one is loc. Let's see where n minus one is located.

[01:19:42]And you see that this n minus one is in the in this child's sub tree. So let's call this as as the heavy child. So this is the heavy nodes. So these are the heavy nodes.

[01:19:59]This means that these nodes hold a lot of power. Why? Because these nodes, one of these nodes holds the power. Not just one. There could be multiple such nodes that holds the power. Like what if there is n minus2 hiding over here? This n minus2 itself could clear everything on the right hand side. So these nodes are heavy nodes because they hold the power to delete all the other nodes. So let's call all the other branches, all the nodes in all the other child branches as the light nodes. So these are your light nodes.

[01:20:35]So these are your light nodes.

[01:20:42]So when can n enter the set? So you can see that n can enter the set only after a heavy element has entered the set.

[01:20:53]Because if a light element has entered the set after this n cannot enter.

[01:21:00]Why? because this element will have to expose n as a leaf but then this x has to delete the biggest element of the heavy set which is n minus one.

[01:21:15]So this means that n can enter the set after any element of the heavy set as long as this element x suppose this element that you are dealing with is this x. The question is can n enter the set after this x? That is if x is the pivot then can x clear everything and then let n enter into the set. So can you pause this video and try to think of what is the criteria with which you can decide whether an element of the heavy set can allow n to enter next. So you can see that if the answer the answer is this if if x is greater than the maximum of the light set.

[01:22:12]So if this element alone is greater than the maximum of all the elements in the light set then this means that it is powerful enough to delete all the elements from the light set and it is powerful enough to expose the root as the leaf element and then you have found one way for n to append to an existing element and of course n minus one by definition holds this power because n minus one is of course powerful enough to clear this entire light set. But what if all the heavy heavy elements are present on top and then there is this x.

[01:22:54]So this x only has to clear all the elements of the light set on the right hand side that you see. So to find dp of n, you just have to iterate through all the elements on the heavy set and then you have to check if each element is greater than the maximum element of the light set. If it is then you add its contribution to n. So this might sound a bit complicated but it's not that complicated. If you try to if you try to uh do some analysis on paper it's not that complicated. I'm just talking about heavy and light and that that might confuse things but other than that I think it's pretty simple. So all that remains is to find out which elements are heavy and which elements are light.

[01:23:39]So how do you do that? To do that you just have to do a DFS and this is also normal standard 3D DP or or normal DFS whatever you want to call it. So you can say that if the parent is heavy because this is if the parent is heavy then all the children and all the subree will be heavy. If the parent is light if this is a light set if the parent is light then the entire thing needs to be propagated down as the light set. And how do you figure out if this parent is heavy or not? So to determine if this node is heavy or not, you just have to look at in which sub tree is n minus one present. Now if n minus one is hiding over here, then when you compute the max below of this, it would turn out to be n minus one, right? So if the max below if n minus one could also be here as well, no doubt. So if the maximum of max below of this and this is n minus one it means that this is the heavy set and you propagate heavy downwards. Otherwise all the other child are light and then you iterate through all the light child and you compute their maxima and for each heavy set you compute whether it it can delete all the light child or not. So all of these sounds complicated but it will look simple when you look at the code. So finally let's look at the code.

[01:25:11]So if you want to compute which set are light versus which set are heavy then you can see that if you are if you are a heavy set which is if if it is guaranteed that you are heavy set then there is no doubt about it all all of your subree will also be in the heavy set right so you simply propagate it down like so but if if this is the root if this is the first time you are doing the DFS that is if this is the root element then you figure out Where in which roots children does n minus one?

[01:25:44]Basically in this zero notation it will become n minus2. You figure out in which child if root has five child then only one child will be heavy and five child and four child will be light. So suppose if this is the heavy child and here here you pass heavy is equal to true then all the sub tree in this child will inherit heavy and all the sub tree in this child will inherit light. So you can see that here also dpon tree is doing its trick. It's just that it's not obvious.

[01:26:21]And with just this simple DFS, you can classify nodes into two categories. Heav heavy nodes and light nodes.

[01:26:29]And then finally, you can see that you you want to find out what is the maximum value in the light child. So that if you can if this is the heavy node, if these are the heavy nodes then you want to find out okay if this is the maxima and the light set. If this is your light set right this is your light set. If this is your maxima then if you can clear this maxima then you can clear this entire sub tree and you can expose this root right. So you figure out what is the maxima in the light set and then you iterate through the heavy set and if this heavy set if they if they can clear the maxima if they can delete the maxima it means that they can delete all the light sets or all the light subree it means that root can join that heavy element at the end and that's how you compute the DP value of the root and in this problem you have to find out the answer when the process ends at the root and that's what made it a bit complicated I would say with that heavy and light thing but otherwise if I had to if I had told you that find me the number of ways where you can add end the process at max at n minus one then your original DP would have worked because all we are doing is just we are just taking this original DP and we know that whatever information this DP computes will be correct the information that it does not compute root which is dp of n that part we have to compute manually via heavy and light shield.

[01:28:05]So that's what that was all for the video. Let me know if you have any feedback for