시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 326 | 154 | 115 | 44.402% |
n개의 정점과 n - 1개의 간선으로 구성된 트리 T가 있다. 정점 번호는 0부터 n - 1까지이고 0번 정점이 루트이다. 간선에는 가중치가 없다. 트리 T의 각 정점을 white또는 black으로 색칠하려고 한다. 단, 이웃한 두 정점의 색은 서로 달라야 한다. 각 정점마다 white, black으로 색칠하는 비용이 주어진다. 트리 T의 모든 정점을 색칠하는 최소 비용을 출력하자.
첫 번째 줄에 정점의 수 n이 주어진다.
두 번째 줄부터 n - 1개 줄에 걸쳐 간선의 정보가 주어진다. 한 줄에 하나의 간선 정보가 주어진다. 하나의 간선 정보는 부모 정점 번호 p와 자식 정점 번호 c가 공백을 사이에 두고 순서대로 주어진다.
다음 줄부터 n개의 줄에는 0번 정점부터 n - 1번 정점까지 정점을 색칠하는 비용이 순서대로 주어진다. 한 줄에 하나의 정점을 white, black으로 색칠하는 비용 w, b가 공백을 사이에 두고 순서대로 주어진다.
첫 번째 줄에 트리 T의 모든 노드를 색칠하는 최소 비용을 출력한다.
8 0 1 0 2 1 3 1 4 2 5 2 6 6 7 10 20 10 30 10 100 100 50 50 50 10 50 10 50 70 100
310
0번 정점을 black, 1번 정점을 white, 2번 정점을 white, 3번 정점을 black, 4번 정점을 black, 5번 정점을 black, 6번 정점을 black, 7번 정점을 white로 색칠하는 비용 310이 정답이다.