Internet Problem Solving Contest

• Correct output – D1
• Correct output – D2
• Program solving both data sets

This was supposed to be one of the hard problems in the contest, and, indeed, it was. The easy input could be solved by branch and bound (backtracking) techniques, but for the difficult one heavy machinery of dynamic programming was needed.

We can solve this problem by dynamic programming. We will proceed from the leaves of the tree up to the root. Consider a tree T rooted at a vertex v_T. Let

• n_T be the number of vertices in the tree T
• p_T[k] be the maximum amount of tension that can be relieved in the tree T, provided that exactly k vertices of T are playing in different team than the root v_T.

If T consists of a single vertex, clearly p_T[0] = 0 and p_T[k] is undefined for k>0.

Now consider two trees: T with root v and S with root u. Suppose we have already computed the arrays p_T[] and p_S[]. We will create a new tree W out of S and T by attaching the vertex u, as a child of v. Clearly, using this operation one can build an arbitrary tree out of isolated vertices. Let's see how can we compute the array p_W[].

Consider the value p_W[k]. To get exactly k vertices of W be in a different team than v, it must be the case that i vertices from T and k-i vertices from S are not in team with v for some 0 ≤ i ≤ k. There are two possibilities: either u and v are in the same team, or they are not. In the first case, the amount of tension relieved is p_T[i] + p_S[k-i].

If u and v are in different teams, we want exactly k-i vertices of S to be in the same team as u or, put another way, n_S - (k-i) vertices of S to be in different team than u. In this case, the tension of u is also relieved by t_u and the total amount of tension in W is p_T[i] + p_S[n_S -k+i] + t_u.

Thus the optimal value of p_W[k] is the maximum of p_T[i] + p_S[k-i] and p_T[i] + p_S[n_S -k+i] + t_u over all i such that p_T[i] and p_S[k-i]   (p_S[n_S -k+i] respectively) is defined.

To compute p_T[] for a subtree T rooted at some vertex v, we first recursively compute the arrays p_S[] for all trees S such that S is a subtree rooted at a vertex u, vhich is a child of v. Then, using the relation derived above, we add children of v one at a time and each time recompute p[] for the tree currently hanging from v.

In the end, the value of the optimal solution can be just read off from p_T[N/2], where T is the whole tree and N is the number of vertices. To get the actual division of vertices into teams, one has to trace back through the p_T[] arrays.