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

면접 대비

시간 제한3초메모리 제한512 MB

요약

트리의 각 정점을 흰색 또는 검은색으로 칠합니다. 인접한 두 정점이 모두 검은색이 되지 않도록 하면서 전체 비용의 최소값을 구합니다.

문제

정점 $n$ 개와 간선 $n - 1$ 개로 이루어진 트리 $T$ 가 있다. 정점 번호는 0부터 $n - 1$ 까지이고, 0번 정점이 루트이다. 간선에는 가중치가 없다.

트리 $T$ 의 각 정점을 white 또는 black으로 색칠하려고 한다. 단, 이웃한 두 정점을 모두 black으로 색칠할 수 없다. 즉, 이웃한 두 정점은 white와 black, black과 white, 또는 white와 white로 색칠해야 한다.

각 정점마다 white로 색칠하는 비용과 black으로 색칠하는 비용이 주어진다. 트리 $T$ 의 모든 정점을 색칠하는 최소 비용을 출력하자.

첫 번째 줄에 정점의 수 $n$ 이 주어진다.

두 번째 줄부터 $n - 1$ 개 줄에 걸쳐 간선의 정보가 주어진다. 한 줄에 간선 하나의 정보가 주어진다. 부모 정점 번호 $p$ 와 자식 정점 번호 $c$ 가 공백을 사이에 두고 순서대로 주어진다.

다음 줄부터 $n$ 개의 줄에는 0번 정점부터 $n - 1$ 번 정점까지 정점을 색칠하는 비용이 순서대로 주어진다. 한 줄에 정점 하나의 white로 색칠하는 비용 $w$ 와 black으로 색칠하는 비용 $b$ 가 공백을 사이에 두고 순서대로 주어진다.

첫 번째 줄에 트리 $T$ 의 모든 정점을 색칠하는 최소 비용을 출력한다.

예제 1

입력

예상 출력