Statement:
Given a tree of N nodes, every node i have a value A[i].
You have to find the maximum value you can get by picking a subtree (a subgraph of the tree which is also a tree) of exactly K nodes.
Constrain : 1 <= K,N <= 1000
This can be solve in O(n^3) by a simple dp, but after spending time thinking, I couldnt find a better solution. Can anyone solve this in O(n^2) ?
Help is appreciated.
Perhaps I don't understand something about this problem, but why can't you just do two rounds of DFS?
1st round cumulates the size of each node's subtree. 2nd round cumulates the total value of a subtree.
Then do an O(n) for loop passing through each node, checking if its first round result = K, and then taking the maximum of those second round results.
I don't think DP is needed. Are you sure you understood the problem correctly? ;}
Tree is not rooted, so connected component do not have root is DFS tree too.
I think this is standard knapsack dp in $$$O(n^2)$$$: $$$dp_{i,j}$$$ — maximum result for node $$$i$$$, where $$$i$$$ is included in result and $$$j$$$ its children.
Now it is standard knapsack over direct sons of node $$$i$$$, just iterate until size of each node, not $$$n$$$ and it will be good complexity.
Yup, it's $$$O(n^2)$$$. The code below will always print a number that doesn't exceed $$$n^2$$$ because every pair of vertices contributes to the number of operations at most once (when $$$v$$$ is their LCA).
I am not sure how this is relevant to the time complexity analysis, can you elaborate?
To compute dp of a parent, we iterate over the number of vertices taken in child1 and child2.
I thought that we can take more than 2 children, right?
Merge them one by one
Oh hm, this makes sense. Thanks a lot!
Can you please share your code Errichto
Share your code first ;p You have thousands of problems with code in the Internet. Why do you need me to implement this one too?
Actually when I read the problem i thought it could be implemented with in-out dp but now the solution says O(n^2). I just wanted to know the right answer to this. Btw its 3 AM and you want me to code !!
Oh, I'm sorry I wanted you to code xd
I don't know what in-out dp is, but you can implement n^3 solution and if will be n^2 if you iterate up to child subtree size only.
I think it's still O(n^3) because you have to iterate the number of i's children also.
Why would you do that? You only care about the number of taken vertices and its value is up to
size_of_subtree[child]Do you mean
dp[i][j]wherejis the number of direct children ofior total number of vertices in subtree ofithat we take?EDIT: got it,
jshould be the total number of vertices we take. Then it makes sense.Can you please share your code allllekssssa
https://github.com/Nikitosh/SPbAU-Generation-Z-Team-Reference/blob/master/Graphs/dp_tree.cpp
Check it here
If so, you can modify my solution to loop over the n possible roots. That would be O(n) * O(n) = $$$O(n^2)$$$.