need help with dp on tree
Разница между en1 и en2, 22 символ(ов) изменены
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 
inby a o(n * *k^2) dp solution,↵
please help me to solve in a better complexity. sorry for my english and thanks in advanced

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский minhnhatle 2023-01-30 14:33:12 22
en1 Английский minhnhatle 2023-01-30 14:31:58 434 Initial revision (published)