**problem** : in a rooted **binary** tree with n nodes, each node has a positive value( v(i) ) you need to select k(k<=n) nodes from the tree. if a node is selected you must select all of its ancestors.design a dp algo for maximum possible value of k selected nodes

First, let's observe that it's never optimal to select a non-leaf node. If the constraint are small enough (

n*k^{2}≤ 10^{8}) or something like that, then the following solution will work.Now let

val_{i}be the value associated with nodeiandDP[v][k] be the maximum value we can achieve by selectingknodes on the subtree rooted atv. Ifvis a leaf, thenDP[v][k] =val_{v}fork= 1 and 0 otherwise. Ifvis not a leaf, letlandrbe its left and right children, then recurrence isDP[v][k] =max(DP[l][x] +DP[r][k-x]) +val_{v}for x in range [0,k].Do you have a link to the problem?