### LittleFlowers__'s blog

By LittleFlowers__, history, 5 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.

• +17

 » 5 weeks ago, # |   0 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? ;}
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ |   +21 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;
•  » » » » 4 weeks ago, # ^ |   0 I am not sure how this is relevant to the time complexity analysis, can you elaborate?
•  » » » » » 4 weeks ago, # ^ |   +8 To compute dp of a parent, we iterate over the number of vertices taken in child1 and child2.
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I thought that we can take more than 2 children, right?
•  » » » » » » » 4 weeks ago, # ^ |   +8 Merge them one by one
•  » » » » » » » » 4 weeks ago, # ^ |   0 Oh hm, this makes sense. Thanks a lot!
•  » » » » » » » » 4 weeks ago, # ^ |   -8 Can you please share your code Errichto
•  » » » » » » » » » 4 weeks ago, # ^ |   0 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?
•  » » » » » » » » » 4 weeks ago, # ^ |   -8 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 !!
•  » » » » » » » » » 4 weeks ago, # ^ |   +9 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.
•  » » » 4 weeks ago, # ^ |   0 I think it's still O(n^3) because you have to iterate the number of i's children also.
•  » » » » 4 weeks ago, # ^ |   0 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 →   0 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.
•  » » » 4 weeks ago, # ^ |   -8 Can you please share your code allllekssssa
•  » » » » 4 weeks ago, # ^ |   0
•  » » » 4 weeks ago, # ^ |   -11 If so, you can modify my solution to loop over the n possible roots. That would be O(n) * O(n) = $O(n^2)$.