문제
작은 마을의 이장이 된 현서는 이 마을의 모든 도로가 비포장임을 깨달았다.
이에 현서는 주민들의 편의를 위해, 마을에 있는 도로를 포장하려고 한다.
이 마을에는 N개의 농가가 있고, (N-1)개의 도로가 있으며, 어떤 두 농가를 골라도, 한 곳에서 다른 곳으로 가는 경로는 유일하다.
현서의 마을은 예산이 한정적이기 때문에, 최대한 적은 예산으로 모든 도로를 포장하려고 한다.
도로를 포장하기로 한 날, 마을 주민들은 각자의 거주지에서 다른 농가로 농사를 지으러 갈 것이다.
구체적으로, i번 주민은 이 날 농가 xi에서 농가 yi로 트랙터를 타고 농사를 지으러 간다.
트랙터는 각각 고유의 값 ci를 가지고 있는데, ci가 낮을수록 좋은 트랙터이다.
현서는 어떤 주민의 이동 경로가 비포장이면, 해당 주민의 도움을 받아 도로 하나당 ci의 비용을 들여 그 경로상에 있는 어떤 도로든지 포장할 수 있다.
두 명 이상의 주민이 같은 도로를 지나간다면, 그 중 어느 주민의 도움을 받든 상관이 없다.
어떤 도로는, 외부 업체의 도움을 받는 것이 나을 수도 있다.
(혹은 외부 업체를 부르는 선택지밖에 없을 수도 있다.)
외부 업체의 경우, 어느 도로든 상관없이 도로 하나당 K의 비용을 들여 포장할 수 있다.
예를 들면, 아래의 그림 1과 같은 마을이 있고 이 마을에 주민이 2명 살고 있다고 하자.
(그 마을은 정말 고요할 것이다.)
외부 업체에서 도로 하나를 포장하는 비용 K=5라고 하자.
그림 1
한 주민은 4번 농가에서 3번 농가로 c1=1의 트랙터를 타고 이동할 계획이며.
다른 주민은 5번 농가에서 6번 농가로 c2=3의 트랙터를 타고 이동할 계획이라고 하자.
그러한 경우는 그림 2와 같이 14의 비용을 들여 모든 도로를 포장할 수 있다.
그림 2
현서가 모든 도로를 포장하는 최소비용을 계산하는 프로그램을 작성하라.
입력
첫 줄에 농가의 수인 N과 외부 업체의 도로 포장 비용인 K가 주어진다.
둘째 줄부터 다음 N-1개의 줄에 걸쳐서, 도로의 정보가 u v의 형태로 주어진다.
이는 농가 u에서 농가 v로 가는 도로가 있다는 뜻이다.
그 다음 줄에 주민의 수인 M이 주어진다.
그 다음 M개의 줄에 걸쳐서 도로를 포장하기로 한 날 주민들의 이동정보가 주어진다.
이는 xi yi ci의 형태로 주어지는데, xi에서 yi로 ci의 고유값을 가진 트랙터를 타고 이동한다는 뜻이다.
[부분문제의 제약 형식]
모든 부분문제에 있어서 1≤N≤200,000, 1≤K≤10,000, 1≤M≤200,000이다.
(문제를 잘 읽어보면, 마을이 작다고 했지, 농가 숫자가 적다고는 안 써져 있다는 걸 알 수 있다.
따라서 문제 출제자는 아무 죄가 없다.)
모든 부분문제에 있어서, 1 ≤ u , v , xi , yi ≤ N이고, 1≤ci≤10,000이다.
u≠v , xi≠yi 이다. 모든 입력값은 정수이다.
출력
모든 도로를 포장하는데 드는 최소비용을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 8점 | N≤10 , M≤10 |
| #2 | 2점 | 모든 i값에 대해서, K≤ci를 만족한다. |
| #3 | 40점 | N≤10,000 , M≤10,000 |
| #4 | 50점 | 아무 제약조건이 없다. |
예제
7 5
1 2
1 3
2 4
2 5
3 6
3 7
2
4 3 1
5 6 3
14
로그인해야 코드를 작성할 수 있어요.