negativez2's blog

By negativez2, history, 5 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it