minhnhatle's blog

By minhnhatle, history, 14 months ago, In English

given a tree of n node , each node has a lable c[i] , we need to choose k nodes such that they are connected with each other and the sum of lable of k nodes is maximum. k <= n <= 5000, |c[i]| <= 10^5

input: n = 3, k = 2, c = {1, 2, 3} , edge of the tree: (1, 2), (2, 3) output: 5

i can only solve by a o(n*k^2) dp solution, please help me to solve in a better complexity. sorry for my english and thanks in advanced

Tags tree, dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

It would be great if you share the problem link.