시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 643 | 188 | 160 | 35.477% |
N개의 노드를 가지고 있으며, 루트가 있는 트리의 각 노드에 가중치가 부여돼 있다. 임의의 노드의 번호를 i라 하고, i번 노드에 부여된 가중치를 C[i]라 한다.
이 트리를 색칠한다고 상상해 보자. 한 노드를 색칠하는 데에는 비용이 드는데, i번 노드가 F[i]번째로 색칠되는 노드라면, i번 노드를 색칠하는 데 드는 비용은 C[i]*F[i]로 계산된다. 전체 트리를 색칠하는 데 드는 비용은 각 노드를 색칠하는 데 드는 비용의 합이다.
단, 어떤 노드를 색칠하기 위해서는 그 노드의 부모 노드가 이미 색칠되어 있어야 한다. 따라서 루트가 가장 먼저 색칠되어야 한다. 이러한 규칙에 따를 때, 최소의 비용으로 트리를 색칠하는 프로그램을 작성하시오.
첫째 줄에 트리 내 노드의 수 N과, 루트의 번호 R이 공백을 사이에 두고 주어진다. (1 ≤ N ≤ 1,000. 1 ≤ R ≤ N) 둘째 줄에는 C[i]가 차례로 주어진다. 이후 N-1개의 줄에는 트리 내의 간선이 두 개의 자연수로 주어진다. 두 수가 U, V라면 U번 노드와 V번 노드 사이에 간선이 있으며, U가 V의 부모라는 뜻이다.
첫째 줄에, 트리를 색칠하기 위한 최소 비용을 출력한다.
5 1 1 2 1 2 4 1 2 1 3 2 4 3 5
33
1, 3, 5, 2, 4의 순서대로 색칠을 하면 차례로 1×1, 2×1, 3×4, 4×2, 5×2의 비용이 들어서 총 33의 비용이 들게 된다.
ICPC > Regionals > Asia East Continent > China > Beijing > Beijing Regional Contest 2004 F번