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 $$$4$$$, but it prints $$$5$$$.

can you please get the right algo for this question?

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) ?

Your first algorithm is $$$O(n)$$$, but it's wrong (because a correct algorithm should run at least in $$$O(n \log n)$$$), so it doesn't matter.

The 2D DP should be $$$O(n^2)$$$.

Ok thanks. So the 2D DP one is correct and runs in $$$O(n^2)$$$ right ? It won't fail for any case right ?

Also, do you have any idea for nlogn solution that works. Is it similar to the first comment I posted on this blog ?

If you have written the 2D DP correctly, it's correct :D

In my first comment, I have posted a $$$O(n \log n)$$$ solution.

Could you please explain how do we backtrack to get the final rooted minor which is a heap in our solution. Will it be like the following -

We start doing DFS from the root node, if its nottake value > take value, we contract this edge and not add it in the final solution.

For this we need to store values of take, nottake separately.

Read this blog. It should work in any DP without memory optimizations.

Sorry for repetitive questions but you have been very helpful and appreciate it.

void maketree(int index, int num){
	if(dp[index][num][1] > dp[index][num][0]){
		for(auto x: adj[index]){
			maketree(x,index);
		}
		if(index!=num)
			newadj[num].push_back(index);
	}
	else{
		for(auto x: adj[index]){
			maketree(x,num);
		}
	}
}

Is the above function for backtracking and getting the largest rooted minor which is a min heap correct ? Here dp[index][num][1] corresponds to take and dp[index][num][0] corresponds to nottake. If correct, time complexity is O(N) ?

Explanation if someone wants to understand:

Case 1 opt take > opt nottake: In this case, since we are taking the current node, we call the maketree() function for the children of this node and pass value(node) as the parameter to make sure heap property is satisfied. Since we are taking this node, we create an edge between the calling node and this node in a new tree which will finally becomes our largest min-heap rooted minor.

Case 2 opt take ≤ opt nottake: In this case, since we are not taking the current node, we will call the maketree() function for the children of this node but this time we pass the same val as parameter. This is because we don’t need to check for heap property for current node

Once again, thanks a lot for your help.

I think I don't understand something in your code. maketree is called only once for each node. Then, for each index, you create at most one edge to other nodes.