| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 110 | 22 | 12 | 22.222% |
Seoul City Mayor Hanbyeol plans to build a subway system to alleviate traffic congestion on its jam-packed roads. However, due to budget constraints, only a maximum of $K$ stations can be built, and a single path of roads must connect all the stations.
Specifically, when the layout of Seoul can be represented as a connected graph with $N$ nodes and $N-1$ bidirectional edges, where a node represents a building and an edge represents a road, Hanbyeol must select a simple path of $X$ nodes, where $1 \le X \le K$, and build stations on every node along that path.
Hanbyeol wants to minimize the maximum distance between the buildings to the nearest station. To help Hanbyeol, write a program that determines the best location for the subway stations so that such value is minimized.
The first line of input contains two space-separated integers: $N$, denoting the count of the nodes in the city, and $K$, denoting the count of the maximum subway stations that Hanbyeol can build. ($1 \le K \le N \le 300\,000$)
The $i$-th of the next $N-1$ lines of input contains three space-separated integers: $u_i$ and $v_i$, denoting the indices of nodes that the $i$-th road is connecting, and $l_i$, denoting the length of the $i$-th road in kilometers. ($1 \le u_i, v_i \le N;$ $1 \le l_i \le 10^{12};$ $i \ne j \rightarrow \{u_i,v_i\} \ne \{u_j,v_j\}$)
Output the maximum distance from any building to the nearest subway station when it is the minimum possible, in kilometers.
Modified constraints apply: $1 \le K \le 4;$ $1 \le N \le 40$.
Modified constraints apply: $K=1;$ $1 \le N \le 300\,000$.
A ‘subway system’ with just one station? That's insane!
Modified constraints apply: $1 \le K \le N \le 2\,000$.
Original constraints apply: $1 \le K \le N \le 300\,000$.
9 3 1 2 5 2 3 8 3 4 6 3 5 9 5 6 8 5 9 11 6 7 1 6 8 12
13
9 5 1 2 5 2 3 8 3 4 6 3 5 9 5 6 8 5 9 11 6 7 1 6 8 12
11
This test corresponds to the Subtask 3.
(For Sogang students:) Note that this problem is an improvised version that matches the format of a problem in a general programming contest. While in the exam, the original scoring was:
University > 서강대학교 > CSE4152 문제해결프로그래밍실습 > 2024-2학기 중간고사 코딩 테스트 5번