| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 137 | 48 | 39 | 35.780% |
JOI나라에는 $N$개의 도시가 있다. 이 도시들은 1번부터 $N$번까지 번호가 붙어있다. 이 도시에는 $N-1$개의 도로가 있고, 1번부터 $N-1$번까지의 번호가 붙어있다. $i$번 (1ドル \le i \le N-1$) 도로는 노선이 두개가 있다. 한 노선은 $A_i$번 도시에서 $B_i$번 도시로 향하는 노선이고, 다른 노선은 $B_i$번 도시에서 $A_i$번 도시로 향하는 노선이다. 즉, 모든 도로는 양방향이다. 어떤 두 도시간에도 몇개의 도로를 사용해서 이동하는 것이 가능하다.
처음에 모든 노선들은 정비되어있지 않다. 각 도로의 각 노선에 대해, 우리는 노선을 정비하는 비용을 알고 있다. $i$번 (1ドル \le i \le N-1$) 도로의 $A_i$번 도시에서 $B_i$번 도시로 향하는 노선을 정비하는 비용은 $C_i$이고, $B_i$번 도시에서 $A_i$번 도시로 향하는 노선을 정비하는 비용은 $D_i$이다.
JOI나라의 장관인 K이사장은 몇몇 도시를 돌라 그 도시를 특별관광도시로 만들것이다. $x$번 (1ドル \le x \le N$)을 특별관광도시로 만들 때, 각 도로 $i$(1ドル \le i \le N-1$)에 대해, 다음 일이 일어날 것이다.
특별관광도시를 만들기 위해 노선을 정비하는 비용은 세금으로 충당되지만, 특별관광도시가 만들어 진 이후에 남은 도로를 정비하는 비용은 K이사장의 개인 자금에서 나간다.
K이사장이 계획한 $Q$개의 계획이 있다. $j$ 번째 (1ドル \le j \le Q$) 계획에서는, 그는 특별관광도시가 없고 모든 노선이 정비되지 않은 상태에서 시작해서 정확히 $E_j$개의 도시를 특별관광도시로 만들것이다. 하지만, 어떤 도시들이 특별관광도시가 될지는 계획되지 않았다. 그는 개인 자금에서 나가는 도로 정비 비용을 최소로 하고 싶다.
JOI나라의 도시 수, 도로의 정보와 계획의 정보가 주어졌을 때, 각 계획마다 K이사장의 개인 자금에서 나가는 도로 정비 비용을 최소로 하는 프로그램을 작성하여라.
표준 입력에서 다음과 같은 형식으로 주어진다. 모든 값은 정수이다.
$N$
$A_1$ $B_1$ $C_1$ $D_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$ $C_{N-1}$ $D_{N-1}$
$Q$
$E_1$
$\vdots$
$E_Q$
표준 출력으로 $Q$개의 줄을 출력하여라. $j$ 번째 (1ドル \le j \le Q$)줄은 $j$ 번째 계획에서 이사장의 개인 자금에서 나가는 도로 정비 비용의 최솟값이어야 한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | N ≤ 16. |
| 2 | 7 | Q = 1, E1 = 1. |
| 3 | 9 | Q = 1, E1 = 2. |
| 4 | 17 | N ≤ 2 000. |
| 5 | 17 | Q = 1. |
| 6 | 44 | No additional constraints. |
4 1 2 1 2 1 3 3 4 1 4 5 6 2 1 2
9 1
첫 번째 계획은 정확히 하나의 도시를 특별관광도시로 만드는 것이다. 만약 1번 도시를 특별관광도시로 지정한다면, 1번 도로의 2번 도시에서 1번 도시로 향하는 노선, 2번 도로의 3번 도시에서 1번 도시로 향하는 노선, 3번 도로의 1번 도시에서 3번 도시로 향하는 노선이 정비될 것이다. 이 때 정비되지 않고 남는 노선은 1번 도로의 1번 도시에서 2번 도시로 향하는 노선, 2번 도로의 1번 도시에서 3번 도시로 향하는 노선, 3번 도로의 1번 도시에서 4번 도시로 향하는 노선이다. 이 노선들을 정비하는 비용은 1+3+5=9이다. 이보다 더 낮은 비용으로 특별관광도시를 지정하는 방법은 없다. 그래서 답은 9이다.
두번째 계획은 정확히 두 개의 도시를 특별관광도시로 만드는 것이다. 만약 3번 도시와 4번 도시를 특별관광도시로 지정했다면, 도로의 1번 도시에서 2번 도시로 향하는 노선만 정비되지 않았을 것이다. 이 노선을 정비하는데에 드는 비용은 1이다. 이보다 더 낮은 비용으로 두 특별관광도시를 지정하는 방법은 없다. 그래서 답은 1이다.
5 1 3 13 6 5 1 17 8 5 2 6 10 1 4 16 11 1 1
36
6 1 6 6 12 6 2 5 16 1 4 13 4 5 1 19 3 3 1 9 13 1 2
14
Camp > JOI Spring Training Camp > JOI 2018/2019 Spring Training Camp 3-1번