# Tree Pruning

# Tree Pruning

eefasmer + 0 comments I have the following algorithm. I run DFS on the tree and make an array, lets call it postOrder, of the nodes in a post order traversal. The root is the rightmost element of the array. I also build an array maintaining the sizes of all the subtrees, lets call it subtreeSize, such that subtreeSize[i] is the size of the subtree rooted at i. Then comes the dynamic programming part where I will be working on the postOrder array from left to right, such that root 1 is the last element to be handled. I initialize an array DP of dimensions n + 1 and k + 1 and set dp[0][j] = 0 for all j. The dp formula I use is: dp[i][j] = max { dp[i-1][j] + weight[i], dp[i-subtreeSize[i]][j-1]}. The rationale behind the formula is that either I don't remove the i-th element (dp[i-1][j] + weight[i]) or I do (dp[i-subtreeSize[i]][j-1]). Four of the test cases passes and the rest fail. When I debug my dp table at test case 3 I see that dp[n][k] = 16511421728 while the answer is said to be 16234296119, which happens to be the value inside my dp[n][k-1]. Any suggestions to what may be wrong?

EDIT: I just found out what the problem was. I had forgot one more step of the initialization part, namely to set dp[i][0] to sumweight[i-1] + weight[i]. Before I could do this initialization step I had to build the sumweight array. sumweight[i] stores the weights of all the i first nodes of the postorder array. When I added these changes to my code all the test cases passed. I had written everything down on a paper but I forgot to actually add all of it into the code. I hope this explanation will help others solve the problem.

googlichakri + 1 comment Is the input format correct? It has been said that the tree is rooted at vertex 1 But the sample input seems to have nodes directed to vertex 1 5 2 1 1 -1 -1 -1 1 2 2 3 4 1 4 5 As you can see below, if I construct the tree 4 will be the root Please clarify

bharathi_sivara1 + 1 comment I had the same question. The input example 4 1 appears to be incorrect. It must be 1 4 instead.

soumendofadar + 1 comment That is an undirected graph so 4 1 and 1 4 is same.

tomwheyprotein + 0 comments [deleted]

nickarduini + 0 comments Interesting problem. I couldn't meet the time constraints for two of the tests in C++ and was banging my head against the wall. Changed a bunch of my STL containers to arrays and, though a little faster, still no luck. Then I realized I had my inner loop iterating over the first index and outer loop iterating over the second index in my 2d array. I simply switched the inner and outer loops and passed the time constraints easily. Will have to remember that going forward :)

www_jacobian_nxn + 0 comments Is it possible to solve this problem without storing nodes of the tree on the basis of their discovery time i.e. directly while running dfs?

ZHUYUE + 0 comments i failed at the testcase #8 and #9. No idea why......

Marco_L_T + 0 comments The testcases seemed to be weak and my O(n*k^2) passed all tests within the time limit.Admin,would you please add a few more stronger testcases?

googlichakri + 0 comments My answer was incorrect

lduarteoliveira + 0 comments Hi,

This tree is binary? Yes or no?

H_Pandey + 0 comments Can someone please explain the code to me.

knock_out + 0 comments try to print the vector f of the editorial , for cut = 2 and node = 4 it is givin ans 1 but actually this is not expected . it should not be 2 ? because we can remove 3 and 4 both by two cuts ? any comment ??

Sort 23 Discussions, By:

Please Login in order to post a comment