JOI 2018/2019 Spring Training Camp 3-1번- 특별관광도시 > 문제은행 : 정보올림피아드&알고리즘




3626 : 특별관광도시

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
1 회   
시도횟수
2 회   

문제

JOI 나라에는 N개의 도시가 있다. 이 도시들은 1번부터 N번까지 번호가 붙어있다. 이 도시에는 N-1개의 도로가 있고, 1번부터 N-1번까지의 번호가 붙어있다. i번 (1 ≤ i ≤ N-1) 도로는 노선이 두개가 있다. 한 노선은 Ai번 도시에서 Bi번 도시로 향하는 노선이고, 다른 노선은 Bi번 도시에서 Ai번 도시로 향하는 노선이다. 즉, 모든 도로는 양방향이다. 어떤 두 도시간에도 몇개의 도로를 사용해서 이동하는 것이 가능하다.

 

처음에 모든 노선들은 정비되어있지 않다. 각 도로의 각 노선에 대해, 우리는 노선을 정비하는 비용을 알고 있다. i번 (1 ≤ i ≤ N-1) 도로의 Ai번 도시에서 Bi번 도시로 향하는 노선을 정비하는 비용은 Ci이고, Bi번 도시에서 Ai번 도시로 향하는 노선을 정비하는 비용은 Di이다.

 

JOI 나라의 장관인 K 이사장은 몇몇 도시를 골라 그 도시를 특별관광도시로 만들것이다. x번 (1 ≤ x ≤ N)을 특별관광도시로 만들 때, 각 도로 i (1 ≤ i ≤ N-1)에 대해, 다음 일이 일어날 것이다.

 


  • i번과 Bi번 도시 중에서 x번 도시에 가까운 도시는 a번 도시이고, 먼 도시는 b번 도시라고 하자. 여기서, 가까운 도시라고 함은 x번 도시에 가기 위해 사용해야 하는 도로의 수가 더 적은 도시를 말한다. 이 때, b번 도시에서 a번 도시로 향하는 노선이 정비되지 않은 상태라면 정비된다.

 

특별관광도시를 만들기 위해 노선을 정비하는 비용은 세금으로 충당되지만, 특별관광도시가 만들어 진 이후에 남은 도로를 정비하는 비용은 K 이사장의 개인 자금에서 나간다.

 

K 이사장이 계획한 Q개의 계획이 있다. j번째 (1 ≤ j ≤ Q) 계획에서는, 그는 특별관광도시가 없고 모든 노선이 정비되지 않은 상태에서 시작해서 정확히 Ej개의 도시를 특별관광도시로 만들것이다. 하지만, 어떤 도시들이 특별관광도시가 될지는 계획되지 않았다. 그는 개인 자금에서 나가는 도로 정비 비용을 최소로 하고 싶다.

 

JOI 나라의 도시 수, 도로의 정보와 계획의 정보가 주어졌을 때, 각 계획마다 K이사장의 개인 자금에서 나가는 도로 정비 비용을 최소로 하는 프로그램을 작성하여라.​ 

 

<제한>

2 ≤ N ≤ 200,000

1 ≤ Ai ≤ N (1 ≤ i ≤ N) 

1 ≤ Bi ≤ N (1 ≤ i ≤ N) 

A​i != Bi

어떤 두 도시간에도 몇개의 도로를 사용해서 이동하는 것이 가능하다.

0 ≤ Ci ≤ 1,000,000,000 (1 ≤ i ≤ N) 

0 ≤ Di ≤ 1,000,000,000 (1 ≤ i ≤ N) 

1 ≤ Q ≤ N

1 ≤ Ei ≤ N (1 ≤ j ≤ Q) 

 

 


입력형식

표준 입력에서 다음과 같은 형식으로 주어진다. 모든 값은 정수이다.

 

N

A1 B1 C1 D1

.

.

.

AN-1 BN-1 CN-1 DN-1

Q

E1

.

.

.

EQ​ 


출력형식

표준 출력으로 Q개의 줄을 출력하여라. 

j번째 (1 ≤ j ≤ Q)줄은 j번째 계획에서 이사장의 개인 자금에서 나가는 도로 정비 비용의 최솟값이어야 한다. 


입력 예

4
1 2 1 2
1 3 3 4
1 4 5 6
2
1
2

출력 예

9
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

Hint!

입력예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이다.​ 




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP