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 * k2 ≤ 108) or something like that, then the following solution will work.
Now let vali be the value associated with node i and DP[v][k] be the maximum value we can achieve by selecting k nodes on the subtree rooted at v. If v is a leaf, then DP[v][k] = valv for k = 1 and 0 otherwise. If v is not a leaf, let l and r be its left and right children, then recurrence is DP[v][k] = max(DP[l][x] + DP[r][k - x]) + valv for x in range [0, k].
Do you have a link to the problem?