트리 색칠

루트가 정해진 트리에 N개의 노드가 있고, 각 노드에는 가중치가 하나씩 붙어 있다. 노드 i의 가중치를 C\[i]라고 하자.

모든 노드를 하나씩 색칠하려고 한다. 노드 i가 전체 과정에서 F\[i]번째로 색칠된다면, 이 노드를 색칠하는 비용은 C\[i] * F\[i]이다. 전체 비용은 모든 노드의 비용을 더한 값이다.

단, 어떤 노드를 색칠하려면 그 부모 노드가 먼저 색칠되어 있어야 한다. 따라서 루트는 반드시 가장 먼저 색칠된다. 이 규칙을 지키면서 전체 트리를 색칠하는 최소 비용을 구하라.

첫째 줄에 트리의 노드 수 N과 루트 번호 R이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ R ≤ N)

둘째 줄에는 C\[1], C\[2], ..., C\[N]이 차례대로 주어진다.

이후 N - 1개의 줄에는 간선 정보가 주어진다. 각 줄에는 두 자연수 U, V가 공백으로 구분되어 주어지며, 이는 U번 노드가 V번 노드의 부모라는 뜻이다.

트리를 모두 색칠하는 데 필요한 최소 비용을 첫째 줄에 출력한다.

1, 3, 5, 2, 4 순서로 색칠하면 각 단계의 비용은 1 * 1, 2 * 1, 3 * 4, 4 * 2, 5 * 2가 되고, 총비용은 33이 된다.