PROBLEM LINK:Author: Roman Rubanenko DIFFICULTY:MediumHard PREREQUISITES:knapsack, graph theory, tree, dfs. PROBLEM:You are given a rooted tree with N vertices. Vertices are numbered from 1 to N and vertex 1 is the root of the tree. A positive integer W_{i} is assigned to every node. Consider following code:
One can notice that the state of marked[] array depends on the order vertices u processed. You are to check for every integer number s from 1 to the sum of $W_i$ whether there exists some order of viewing children in Dfs that marked[s] = true. ExplanationHow is marked array related to dfs? Note that when we do dfs, we chose the next node to go from the current node. While choosing the next node, we have freedom of choosing any child of current node as the next vertex to do dfs from. This freedom will effect the global variable sum. Hence state of marked[] array will depend on the order of vertices processed in the dfs. Is there some nice property of dfs which can come handy? Note that during dfs, if you are currently at vertex v, then following cases can occur.
Great, Can you we use it somehow in our problem? Let's store boolean array for global answer. The array size is equal to sum of all the weights, it will contain 1 if corresponding weight is achievable, otherwise it will contain zero. So now let's do a dfs from the root and store current knapsack that shows what weights we can get at the moment of visiting current vertex. When we are at some vertex, let's add items with weights equal to the sizes of all the children of this node. By subtree size, I mean the sum of weight of all the vertices who lie in the subtree. When we go down to one of these children, we should delete it's subtree size, go down, return and add the value back. Yes, I understood it, Can you provide some pseudo code? Pseudo Code Can you take one example? Yes, I will try to explain you concept of the knapsack's. Let us have a look at this picture. When we are node 3, we have value of curSum equal to weight of vertices on the path from root to current vertex (ie. vertex 1 and 3). Note that There are following ways of coming at node 3.  We have directly come to node 3(ie. from 1 to 3)  We have visited the left subtree of 1 and then come directly to node 3.  We might have visited the left subtree of 1 and we have come from 1 to 3, then from 3, we have visited one of the subtrees of 3, and have come back to 3. Note that currently, the value of variable sum will be atleast weight of path from root to current (vertex 1 and 3). Other than that, it can be any combination of left subtree of 1, left and right subtree of 3. So we can consider these three subtree's as knapsack's. If you have not understand the details upto now. Please try to create idea for nonrecursive solution (without using dfs). You will get an exact idea about which of the subtrees has to deleted and which of them have to be considered in the knapsack. Yes, I got that. But how will I add and delete items from the knapsack? Yes, So we should be able to handle adding/deleting an item from the knapsack. Let's store number of ways we can get a particular weight rather than storing simple boolean value (whether the weight is achievable or not?). It will allow us to add/delete items. So we can obtain a particular weight if corresponding number of ways is greater than zero. Since the number of ways of obtaining a particular weight can be very huge, we have to store it using modulos some number. Now it is better to use more than one modulo's, It will provide us more accuracy. This is like hashing in some way. tourist's solution uses modulo 10^9 + 7 and 10^9 + 9. Tester's solution contains more than 2 modulos. Can you please explain idea of adding a weight in knapsack with some codes? Yes, if we are adding a weight w into the knapsack. The number of ways of getting value V increase by number of ways of getting weight V  w. Pseudo Code Great, Can you please idea of removing a weight in knapsack with some codes? Yes, if we are removing a weight w from the knapsack. The number of ways of getting value V will decrese by number of ways of getting weight V  w because these were precisely the cases where we had weight V including the current weight w. Pseudo Code Cool, I understood everything. Can we go on the complexity part? Complexity: AUTHOR'S and TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 21 Jul '14, 01:04

[Edit : If you looked at xellos0 answer, you can skip this answer] This O(n * n * W) solution is supposed to fail. http://www.codechef.com/viewsolution/4360304 Are the test cases weak? I am only considering addition into knapsack, doing it O(childCount) times. So it is O(childCount * childCount) which has to time out. I used a different approach in contest which is kind of decomposition when number of one bits in current array are low and that had bad runtime than this n * n * W solution. answered 21 Jul '14, 01:25

I don't understand the part of deleting and adding items in knapsack. How it is done? ' But how will I add and delete items from the knapsack? ' can someone please elaborate ? answered 21 Jul '14, 18:52

the link to tourist's solution is wrong