트리를 간단하게 색칠하는 최소 비용

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

트리 $T$의 각 정점을 white 또는 black으로 칠하려고 한다. 이웃한 두 정점의 색은 서로 달라야 한다. 각 정점에는 white로 칠할 때의 비용과 black으로 칠할 때의 비용이 주어진다.

트리 $T$의 모든 정점을 칠하는 최소 비용을 구한다.

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

두 번째 줄부터 $n-1$개의 줄에 간선 정보가 한 줄에 하나씩 주어진다. 각 간선 정보는 부모 정점 번호 $p$와 자식 정점 번호 $c$가 공백으로 구분되어 순서대로 주어진다.

그다음 $n$개의 줄에는 0번 정점부터 $n-1$번 정점까지 정점별 칠하는 비용이 순서대로 주어진다. 각 줄에는 정수 $w$와 $b$가 공백으로 구분되어 있다. $w$는 white로 칠하는 비용, $b$는 black으로 칠하는 비용이다.

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

• $2 \le n \le 100{,}000$
• $0 \le p, c \le n-1$, $p \ne c$
• 주어진 간선들로 만들어진 그래프는 트리이다.
• $1 \le w, b \le 100{,}000$이며, $w$와 $b$는 양의 정수이다.