"
Suppose we are given a rooted tree T with n leaves and m non-leaf nodes.
Each leaf is colored with one of k < n given colors, so several leaves can
have the same color. We need to color each interior node of T with one of
the k given colors to maximize the number of edges whose (two) endpoints
are colored the same color.
We can solve this with a DP algorithm that runs in O(mk) time. Let V (v,
i) denote the optimal solution value when the problem is applied to the
subtree rooted at node v, and v is required to be given color i. Let V (v)
denote the optimal solution value when the problem is applied to the
subtree rooted at node v, and there is no restriction on which of the k
colors v can be.
a. Using that notation, develop recurrences for this problem, and explain
the correctness of your recurrences.
b. Explain how the recurrences are evaluated (solved) in an efficient DP
way.
c. Show that the time bound for your DP is O(mk).
“
