LittleFlowers__'s blog

By LittleFlowers__, history, 4 weeks ago, , 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. Comments (18)
 » 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). int operations = 0; for(int v : vertices) for(int child1 : children[v]) for(int child2 : children[v]) operations += size_of_subtree[child1] * size_of_subtree[child2]; cout << operations;
•  » » » » 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.
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   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 xdI 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]
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   Do you mean dp[i][j] where j is the number of direct children of i or total number of vertices in subtree of i that we take?EDIT: got it, j should be the total number of vertices we take. Then it makes sense.
•  » » » Can you please share your code allllekssssa
•  » » » »
•  » » » If so, you can modify my solution to loop over the n possible roots. That would be O(n) * O(n) = $O(n^2)$.