| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 22 | 18 | 13 | 81.250% |
셀레스트 산에는 $1$번부터 $N$번까지 번호가 붙은 $N$개의 시계 장치가 있다. 이 시계 장치들은 $N-1$개의 전선을 통해 모두 서로 연결되어 있다. 각 시계 장치는 $1$시부터 $12$시까지 총 $12$가지 중 하나의 시각을 가리킬 수 있다.
시계 장치에는 태엽이 있어, 전선을 통해 연결된 모든 시계 장치의 시간을 한 시간 단위로 돌릴 수 있다. 이때 $12$시에서 $1$시간이 지나면 $1$시가 된다. 두 시계가 전선을 통해 연결되어 있다는 것은 하나 이상의 전선을 거쳐 한 시계에서 다른 시계까지의 경로가 존재한다는 뜻이다.
현재 시각은 $12$시이다. 하지만 현재 $i$번째 시계 장치는 $D_i$시를 가리키고 있다. 만약 $i$번째 시계 장치가 $12$시를 가리키게 맞출 수 있다면, 당신은 그 시계 장치를 올바르게 맞춘 보수로 금화 $W_i$개를 받는다.
처음에 시계 장치들은 모두 연결되어 있으므로, 모든 시계 장치들은 똑같이 돌아간다. 당신은 더 많은 시계를 올바르게 맞추기 위해 전선을 원하는 만큼 끊을 수 있다. 그러나, 하나의 전선을 끊을 때마다 받는 보수는 금화 $C$개만큼 줄어든다.
당신이 보수로 받을 수 있는 금화의 최대 개수는 몇 개일까?
첫 번째 줄에 시계 장치의 수 $N$과 전선을 끊는 데 드는 비용 $C$가 주어진다.
두 번째 줄에 현재 시계 장치가 가리키고 있는 시각 $D_i$가 차례대로 주어진다. ($1 \le i \le N$)
세 번째 줄에 시계 장치를 올바르게 맞추었을 때의 보수 $W_i$가 차례대로 주어진다. ($1 \le i \le N$)
그 다음 $N-1$개의 줄에 시계 장치를 잇는 전선의 번호 $U_i$와 $V_i$가 차례로 주어진다. ($1 \le i \le N - 1$)
이는 $U_i$번 시계 장치와 $V_i$번 시계 장치가 전선으로 이어져 있다는 뜻이다.
첫 번째 줄에 당신이 벌어들일 수 있는 금화의 최대 개수를 출력한다.
7 7 11 11 9 7 7 12 4 6 4 3 7 5 3 2 1 2 2 3 3 4 4 5 4 6 6 7
15
처음 상태에서는, 아무리 시계를 잘 맞춰도 금화 12개까지밖에 얻을 수 없다. 이때 맞춰지는 시계 장치는 4번과 5번이다.
만약 3번 시계 장치와 4번 시계 장치를 잇는 전선을 자른다면, 시계 장치 1, 2를 맞춰 금화 10개, 시계 장치 4, 5를 맞춰 금화 12개를 얻을 수 있다.
총 얻는 금화 22개, 전선을 끊는 데 지불한 금화 7개로 벌어들인 총 금화는 15개이다.
이 예제에서는 이것보다 많이 금화를 벌어들일 수 있는 방법이 없다.