시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB31131144.000%

문제

The city of “문해프” consists of $N$ buildings and $N - 1$ roads, forming a tree structure (meaning that every pair of buildings is connected by exactly one simple path, and there are no cycles.). All roads are bidirectional and have their own lengths.

The newly appointed mayor of “문해프” City plans to divide the city into $K$ regions by removing $K-1$ roads. (if $K = 1$, a single region covers the entire city.) Then, one Network Station will be built in each region to facilitate communication among the buildings within that region.

Each region $R$ contains multiple buildings. The communication complexity of region $R$ is defined as $ \sum_{i,j\in R, i<j} \operatorname{dist}(i,j) $, where the sum runs over all unordered pairs of distinct buildings in $R$. In other words, the communication complexity of a region is the total sum of distances between all pairs of buildings in that region.

The mayor of “문해프” City wants to minimize the maximum communication complexity among all regions. Find the minimum possible value of this maximum communication complexity when the city is divided optimally.

입력

The first line contains two integers $N$ and $K$, the number of buildings and the number of regions to divide the city into. $(K \leq N \leq 100\,000, K \in \{1,2\})$

Each of the next $N-1$ lines contains three integers $a_i$, $b_i$, and $c_i$, indicating that there is a bidirectional road between buildings $a_i$ and $b_i$ with length $c_i$. $(1 \leq c_i \leq 100)$

It is guaranteed that the given graph forms a tree.

출력

Print a single integer: the minimum possible value of the maximum communication complexity among all regions.

서브태스크

번호배점제한
150

$1 \leq N \leq 400, K = 1$

210

$1 \leq N \leq 2\,000, K = 1$

310

$1 \leq N \leq 100\,000, K = 1$

410

$K \leq N \leq 400, K \in \{1,2\}$

510

$K \leq N \leq 2\,000, K \in \{1,2\}$

610

$K \leq N \leq 100\,000, K \in \{1,2\}$

예제 입력 1

4 1
2 1 1
2 3 2
2 4 4

예제 출력 1

21

Since $K = 1$, Region 1 represents the entire city. The communication complexity of Region 1 is dist(1, 2) + dist(1, 3) + dist(1, 4) + dist(2, 3) + dist(2, 4) + dist(3, 4) = 1 + 3 + 5 + 2 + 4 + 6 = 21.

This example satisfies the conditions of all subtasks.

예제 입력 2

5 2
1 2 1
1 3 2
1 4 10
4 5 3

예제 출력 2

6

The communication complexity of Region 1 is dist(1, 2) + dist(1, 3) + dist(2, 3) = 6.

The communication complexity of Region 2 is dist(4, 5) = 3.

In this example, dividing the regions as shown in the figure is optimal, and the answer is max(3, 6) = 6.

This example satisfies the conditions of Subtask 4, 5, and 6.

예제 입력 3

1 1

예제 출력 3

0

The communication complexity of Region 1 is 0.

This example satisfies the conditions of all subtasks.

채점 및 기타 정보

  • 예제는 채점하지 않는다.