시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 18 16 11 91.667%

문제

정점이 $N$개인 트리가 주어진다. 각 정점은 1번부터 $N$번까지 차례대로 번호가 부여되어 있다. $i$번째 간선은 $A_i$번 정점과 $B_i$번 정점을 연결하며, 가중치는 $C_i$다. $(1 \leq i < N)$

트리에서 두 정점 사이의 거리는 그 둘을 잇는 최단경로 상의 간선의 가중치의 최댓값으로 정의한다. 단, 같은 두 정점 사이의 거리는 0으로 정의한다.

트리에 사는 사람들이 $N$개의 모임을 개최하려 한다. $i$번째 모임에는 1 이상 $i$ 이하의 번호를 가진 정점에 사는 사람들이 참석한다. 올해에는 코로나바이러스 전파 상황을 고려해 모임을 $X$개의 장소에서 각자 모인 후, 인터넷으로 진행하기로 했다. 각 모임은 트리 상의 서로 다른 $X$개의 정점 $v_1,\cdots,v_X$에서 이루어진다. 모임마다 고르는 정점은 독립적이다. 정점들이 정해지면 각 사람은 $v_1, \cdots, v_X$ 중 필요한 이동 거리가 최소인 정점 중 하나를 골라 이동하게 된다.

코로나바이러스 전파 상황에 따라 $X$의 값을 $1$부터 $K$까지의 값 중 하나로 정하기로 하였다. 모임을 미리 준비하기 위해 각 모임에 대해, $X$의 값이 $1$일 때부터 $K$일 때까지 사람들이 이동하는 거리의 최댓값의 최솟값의 합을 구하는 프로그램을 작성하시오.

입력

첫 줄에 트리의 정점 개수를 의미하는 정수 $N$과 정수 $K$가 사이에 공백을 두고 주어진다. $(1 \leq K \leq N \leq 300\,000)$

두번째 줄부터 $(N-1)$개의 줄에 걸쳐, 트리의 간선에 대한 정보가 주어진다. $(i+1)$번째 줄에는 세 개의 정수 $A_i,B_i,C_i$가 사이에 공백을 두고 주어진다. $(1 \leq i <N)$. 이는 $A_i$번 정점과 $B_i$번 정점을 연결하는 가중치 $C_i$의 간선이 존재함을 의미한다. $(1 \leq A_i,B_i,C_i \leq N)$

출력

첫 번째 줄부터 $N$개의 줄에 걸쳐, 답을 차례대로 출력한다. $i$번째 줄에는 $i$번째 모임에 대한 답을 출력한다 $(1 \leq i \leq N)$.

예제 입력 1

10 4
5 1 2
1 6 4
6 2 1
2 8 9
8 3 5
3 4 8
4 10 9
10 9 8
9 7 7

예제 출력 1

0
4
13
21
23
23
30
31
33
34

예제 입력 2

8 3
7 3 4
4 5 2
3 6 1
6 8 6
8 5 1
2 5 8
1 5 2

예제 출력 2

0
8
14
16
16
16
18
18

출처

High School > 경기과학고등학교 > 나는코더다 2020 송년대회 H번