P3177 [HAOI2015] Tree Coloring

There is a tree with $n$ nodes, and each edge has a weight. You are given a positive integer $k$ in $0 \sim n$. You need to choose $k$ nodes and color them black, and color the remaining $n - k$ nodes white. After coloring all nodes, you gain a profit equal to the sum of pairwise distances among black nodes plus the sum of pairwise distances among white nodes. What is the maximum possible profit?

The first line contains two integers $n, k$. Lines $2$ to $n$ each contain three positive integers $u, v, w$, indicating that there is an edge $(u, v)$ of length $w$ in the tree. The input guarantees that all nodes are connected.

Output a single positive integer, the maximum profit.

For $100\%$ of the testdata, $0 \leq n, k \leq 2000$. Translated by ChatGPT 5