25690번 - 트리를 복잡하게 색칠하는 최소 비용

문제

n개의 정점과 n - 1개의 간선으로 구성된 트리 T가 있다. 정점 번호는 0부터 n - 1까지이고 0번 정점이 루트이다. 간선에는 가중치가 없다. 트리 T의 각 정점을 white 또는 black으로 색칠하려고 한다. 단, 이웃한 두 정점을 모두 black으로 색칠할 수 없다. 즉, 이웃한 두 정점을 white, black 또는 white, white로 색칠해야 한다. 각 정점마다 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는 양의 정수이다.

힌트