Maximizing Color‐Pair Distance in a Tree

You are given a tree with n nodes (numbered arbitrarily) and each edge has an associated weight. You are also given an integer k (with 1 ≤ k ≤ n). You need to color exactly k nodes black and the remaining n − k nodes white. After coloring, your benefit is defined as the sum of distances between every pair of black nodes plus the sum of distances between every pair of white nodes. The distance between two nodes is defined as the sum of weights on the unique path connecting them.

The task is to determine the maximum benefit achievable by choosing an appropriate set of k nodes to color black.

Formulation using LaTeX:

Let the tree have n nodes and let the chosen black nodes form the set \(B\) (with \(|B| = k\)). Similarly, let the white nodes be in \(W\) (with \(|W| = n−k\)). The benefit is given by:

[ \text{Benefit} = \sum_{\substack{i,j \in B\ i<j}} d(i,j) + \sum_{\substack{i,j \in W\ i<j}} d(i,j), ]

where \(d(i,j)\) is the distance between nodes \(i\) and \(j\). The goal is to maximize the benefit.

Hint: One smart way to attack this problem is to note that the distance between any two nodes is the sum of weights of the edges on the unique path joining them. If you remove an edge \(e\) that splits the tree into two parts with sizes \(a\) and \(b\), and if in one part exactly \(x\) nodes are colored black (and hence \(a-x\) are white), then the contribution of this edge to the final benefit is

[ w_e\Bigl( x(k - x) + (a - x)((n - k) - (a - x) )\Bigr). ]

Using tree-dynamic programming (DP) combined with a knapSack-like merging process, one can decide how many black nodes to assign in each subtree so that the total benefit summed over all edges is maximized. Note that the total benefit can also be seen as the total distance sum over all pairs minus the sum of distances for cross-colored pairs, so maximizing the benefit is equivalent to minimizing the loss from cross-color pairs.

inputFormat

The first line contains two integers n and k, representing the number of nodes and the number of nodes to be colored black, respectively.

Each of the following n − 1 lines contains three integers u, v and w, meaning that there is an edge between node u and node v with weight w.

It is guaranteed that the given graph is a tree.

outputFormat

Output a single integer: the maximum benefit achievable.

sample

3 1
1 2 1
2 3 2

3