Pivoting vertices Let T be a rooted directed tree, not necessarily binary. There
ID: 3570174 • Letter: P
Question
Pivoting vertices
Let T be a rooted directed tree, not necessarily binary. There is a weight associated with each vertex, such that the weight of a vertex is greater than the weight of the vertex's parent. Each vertex can be designated as either a regular or a pivot vertex. The cost of a pivot vertex is the same as its weight. Regular vertices get discounts: their cost is their weight minus the weight of the closest ancestor that is a pivot vertex. Thus, selecting a vertex as a pivot vertex may increase its cost, but it will decrease the costs of some of its descendants. If a regular vertex has no ancestor which is a pivot vertex, then its cost is its weight itself.
There is no limit on the number of pivot vertices. Design an efficient algorithm to designate every vertex as either a regular vertex or a pivot vertex, such that the total cost of all vertices is minimized.
Explanation / Answer
Here's another dynamic program. I'm going to assume that the root must be a pivot node. For each node u, let W[u] be the weight of u. For nodes u and v such that u = v or u is a proper descendant of v, let C[u, v] be the optimum cost of the subtree rooted at u given that u's leafmost pivot ancestor is v. Then we have a recurrence
There is no separate base case because the sum may be empty. The running time is O(number of descendant-ancestor pairs), which is O(n^2).