SUBREM - Editorial

dfs
dynamic-programming
editorial
simple
tree
april19

#42

Thats why they mentioned that 1 is root
:slight_smile:


#43

is this test case correct ?

1
5 2
1 1 -1 -1 -1
1 2
2 3
4 1
4 5


#44

yes it is correct


#45

what is 4 1(last second line), I mean now we have to assume that 4 is the root node, correct?


#47

I tried implementing using dictionary in python, every node is represented as {node num: [value, [pointer 1, pointer 2…], node num 2: [value 2, [pointer 1, pointer…]] }
https://www.codechef.com/viewsolution/24074181 can u check what went wrong.


#48

How come ?

tree is like

                   1
                 /   \
                2     4
               /       \
              3         5

where 1 is root
I guess you are imagining tree incorrectly. can u tell us how tree looks according to you


#49

Its been a while since i coded in python so its difficult to fully understand ur code
but few things i noticed:-

  • why setrecursionlimit manually
  • still not taking 1as root
  • got incorrect output(-5) for given test case when inputs are swapped eg.

1
3 5
1 -5 -10
2 1
3 2


#50

You guys are making easy stuff complicated, not even implementing trees properly…I’ll try to write an editorial on this after my sem :slight_smile:


#51

The tree is undirected. For every node u, v, v can be the parent of u and u can also be the parent of v.


#52
  1. Because edges here are undirected. And you don’t know parent-child relationship between nodes. You just know that 1st node is root.
  2. You are performing DFS on a tree. When you encounter an node and traverse its edges, you need a way to return back to that particular node when you have reached the end of that branch. So you need two-sided edges information
  3. You need to know if that particular has been visited while DFS or not

#53

Or, you can send by value and before every iteration clear the vector.


#54

This will work with only the example case.
Try this input and see what you get
1
6 5
1 -5 -3 2 6 -10
1 3
3 2
4 5
4 1
6 1

see what you get as the answer. The answer should be -1.
You’ll get that by dropping subtree at node 3 and node 6.

Try different test cases. You’ll understand that your logic misses many.


#55

You are adding edges as if it is a directional graph.
adding this line of code should help

graph[d].push_back(s);

that will make is undirected.

Hope it helps.


#56

You’re storing the maximum value possible at a particular node from its subtree. That’s a form of DP. You’re doing that by DFS so that you don’t have to iterate again and again all over the tree from that particular node.
Recursion is being used to do this.


#57

Can someone tell why ( u!=p ) condition is present here. Does it work like visited or not visited :frowning:


#58

it checks if u is not the node in the tree that has already been visited while DFS.
This condition has to be included as the graph is undirected and there are link to connected nodes included in the edges list of both the nodes.
Ex:>

                          1
                       /      \
                    2          3
                  /                \
                5                   4

For the above tree, in the tree adjacency list stored in form of map or vector(depending on what you choose), the edges list of
node 1 will look like 1 -> 2 | 3 | end
node 2 will look like 2 -> 1 | 5 | end
node 3 will look like 3 -> 1 | 4 | end
node 4 will look like 4 -> 3 | end
node 5 will look like 5 -> 2 | end

So while performing DFS, when you start from 1, and go to 2, node 1 has already been visited, and that is why that parameter is passed, so that from node 2, we don’t go back to node 1, but visit the next node, that is node 5. And when we come to node 5, node 2 is passed as the P parameter, so that we dont go back to node 2, but end the DFS on that branch, and retrace back to previous node to perform DFS on next branch.

Hope that helps. :slight_smile:


#59

Thanks, and as stated in the question that we have to minus X.k and k is operation performed, but in tutorial only - x is being passed if sum is negative , why?


#60

Please see the solution again. -x is not being taken straight away.
The maximum(sum of sub-tree, -x) is being taken. That’s because if the sum of that particular subtree is less than -x (for 1 operation being performed on that tree, which is the removal of that sub-tree), then removing that sub-tree is a better option. Because in the trade-off of the sum of that sub-tree and -x, -x is having a higher value.

You can take a look at someone’s solution that probably explains it. If you like, you can look at my solution here.

Hope that helps. :slight_smile:


#61

K (number of operations) is irrelevant here. Because you won’t really need to perform more than 1 removal operation on a sub-tree if its sum is low. You can just remove that whole sub-tree in 1 single operation. Or a branch of that sub-tree, if that branch is bringing down the cumulative sum of that whole sub-tree. Which is why we are using DFS. To save the best value for ever node.


#62

thank you very much, i got it. i thought that for each removal we have to multiply the x and return it, or i can say according to me if 3 subtrees are removed than equation be like : - ( 1x + 2x + 3*x), my mistake :pensive: