트리를 간단하게 색칠하는 최소 비용
면접 대비시간 제한1초메모리 제한512 MB
각 정점의 흰색과 검은색 칠하기 비용이 주어질 때, 이웃한 정점이 다른 색이 되도록 트리 전체를 칠하는 최소 비용을 구한다.
문제
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의 모든 노드를 색칠하는 최소 비용을 출력한다.
제한
- 2 ≤ n ≤ 100,000
- 0 ≤ p, c ≤ n - 1, p ≠ c
- 간선들로 만들어진 그래프는 트리이다.
- 1 ≤ w, b ≤ 100,000, w와 b는 양의 정수이다.