Indian Computing Olympiad

Training Material


Dynamic programming on trees

Dynamic programming is a technique to efficiently compute recursively defined quantities. The recursion is typically with respect to some integer parameters.

We can also define such functions recursively on the nodes of a tree. The idea is to associate a value with each node that combines the values defined for each of its children—in some cases we may process the children in a fixed order. Analogous to regular dynamic programming, we can evaluate such a function bottom up. This is what we call dynamic programming on trees.

For instance, suppose we are given a tree with N nodes and a weight assigned to each node, along with a number K. The aim is to delete enough nodes from the tree so that the tree is left with precisely K leaves. The cost of such a deletion is the sum of the weights of the nodes deleted. What is the minimum cost to reduce to tree to a tree with K leaves?

Let D(v,k) denote the minimum cost to transform the subtree rooted at a vertex v to have precisely k leaves. Then, for any leaf node lv,

  • D(lv,1) = 0
  • D(lv,k) = infinity if k > 1

On the other hand, for any internal node v,

  • D(v,0) = Weight of subtree T(v) rooted at v

Suppose the children of a node v are w1,w2,…,wm. Clearly, the best possible answer, D(v,j), is obtained by taking all possible ways of distributing the j leaves among the m children 1…m and taking the minimum among those.

  • D(v,j) = Minimum     Sum     D(wi,ji)
    j1+j2..jm = j     i

This is not efficient as there are too many choices to be considered. However, we can use dynamic programming once again to compute D(v,j) (for j ≥ 1) by processing the children of j in a fixed order. For this, we need some additional definitions.

Let C(i,j) be the minimum cost of reducing the trees T(w1),…,T(wi) so that together they have j leaves.

  • C(i,0) =     Sum     Wt(T(wk))
        k ≤ i
  • C(1,j) = D(w1,j)
  • C(i+1,j) =     Sum     C(i,j-k) + D(wi+1,k)
        k ≤ j

If we want just one leaf below v, we can either delete all its children and make v a leaf, or retain exactly one leaf amongst the subtrees rooted at its children. This yields the following.

  • D(v,1) = Min ( Sum Wt(T(wi)) , C(m,1) )

Finally, when we need more than one leaf, we cannot make v a leaf, so we need to prune the subtress below the children of v to generate j leaves between them. This gives us

  • D(v,j) = C(m,j) (for j > 1)

We can now use the equations to compute D(v,j) for any value of j using dynamic programming.

Problems based on dynamic programming on trees