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
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.