시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 114 27 25 36.765%

문제

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의 비용이 들게 된다.

출처

ACM-ICPC > Regionals > Asia > China > Beijing > Beijing Regional Contest 2004 F번

  • 잘못된 조건을 찾은 사람: shjgkwo