An interesting/ difficult problem about DP on trees

I came across a good problem in an algorithms textbook and I am not sure if my algorithm is correct or not.The problem goes like this:

Given a tree T where every vertex is assigned a label which is a positive integer, describe an algorithm to find the largest rooted minor that is a minimum heap. Over here A rooted minor of a rooted tree T is any tree obtained by contracting one or more edges. When we contract an edge (u, v), where u is the parent of v, the children of v become new children of u and then v is deleted. From this we can see that the root of the tree should always be part of any rooted minor.

What would be an optimized algorithm, could anyone please explain the recurrence relation for the DP solution. Any help would be appreciated!.

UPDATE: I have attached 2 possible solutions as comments, can someone verify the correctness please

• 14 hours ago, # ^ | ← Rev. 2 →   0 Could you please give an edge case for the Code that I have posted in the comments. It works for all cases I tried but I feel there might be some edge case.

  • 14 hours ago, # ^ | Try lines of length >10>10, and compare your answer with the length of the LIS.

    • 13 hours ago, # ^ | I run the above code for the tree 10 -> 1 -> 11 -> 2 -> 3 -> 12 -> 13 -> 5 -> 7 -> 14 -> 8 -> 9 and got the correct answer which is 5. Is this the correct case ? Also, could you please analyse the complexity of the code in the comments. I think it should be O(n) because we are considering every node a constant number of times. But I don't know how to explain it properly. Can you/anyone write it a bit formally. Thanks

      • 11 hours ago, # ^ | Isn't the correct answer 77?

        • 11 hours ago, # ^ | ← Rev. 2 →   0 According to the question, root should always be part of the rooted minor. This is because we can never delete the root of the Tree by contracting an edge since it does not have a parent. So our answer should always contain the node with value 10.

          • 11 hours ago, # ^ | Ok sorry, I thought the input was in the opposite direction. Can you send the complete code? (I will try to test)

            • 11 hours ago, # ^ | ← Rev. 2 →   0 #include<bits/stdc++.h> using namespace std; vector<int> adj[1000]; vector<int> dp(1000); vector<int> tree(1000); int dfs(int index, int num){ // dp to store previous values if(dp[index] != 0 and index>num){ return(dp[index]); } int nottake = 0; for(int i=0;i<adj[index].size();i++){ nottake += dfs(adj[index][i],num); } int take = 0; if(index >= num){ for(int i=0;i<adj[index].size();i++){ take += dfs(adj[index][i], index); } take++; } dp[index] = max(take,nottake); if(dp[index]==take && take+nottake>0){ tree[index]=index; } else{ tree[index]=-1; } // cout<<take<<" "<<nottake<<" "<<index<<endl; return(max(take,nottake)); } int main(){ // HOW TO RUN - // Replace n with the number of nodes that have children (hardcode) int nodes; // For input, put the value of the nodes that have children and its number of children. // Then enter the values of the children for(int i=0;i<nodes;i++){ int x; cin>>x; int n; cin>>n; for(int j=0;j<n;j++){ int c; cin>>c; adj[x].push_back(c); } } // run with root nodes value twice cout<<dfs(7,7)<<endl; } Sample input would be to replace nodes with 2, and pass the input as 8 1 11 11 2 9 10 Here 8 has 1 child which is 11 and 11 has 2 children which are 9 and 10. The answer should be 3 (heap consists of 8,9,10). Call dfs(8,8) since 8 is root. Appreciate your help :)

              • 9 hours ago, # ^ | ← Rev. 4 →   0 5 1 1 5 5 1 6 6 1 2 2 1 3 3 1 4 If my understanding of the input format is correct, this should print 44, but it prints 55.

              • 8 hours ago, # ^ | can you please get the right algo for this question?

              • 17 minutes ago, # ^ | ← Rev. 2 →   0 Yeah thanks, I tried to resolve the same using 2D DP where I store both index,num in dp and it worked. Also can you please let me know the running time of the above algo, is it O(n) ?

• 5 hours ago, # ^ | thanks