Minimum cost to color a tree

There is a tree $T$ with $n$ vertices and $n-1$ edges. Vertex numbers run from 0 to $n-1$, and vertex 0 is the root. The edges have no weights.

You want to color each vertex of $T$ either white or black. Two adjacent vertices must have different colors. Each vertex has a cost for coloring it white and a cost for coloring it black.

Find the minimum total cost to color all vertices of $T$.

The first line contains the number of vertices $n$.

Each of the next $n-1$ lines contains one edge as two integers, the parent vertex $p$ and the child vertex $c$, separated by a space.

Each of the next $n$ lines gives the costs for one vertex, in order from vertex 0 to vertex $n-1$. Each line has two integers $w$ and $b$, separated by a space. $w$ is the cost to color the vertex white, and $b$ is the cost to color it black.

Print the minimum cost to color all vertices of tree $T$ on the first line.

• $2 \le n \le 100{,}000$
• $0 \le p, c \le n-1$, $p \ne c$
• The edges form a tree.
• $1 \le w, b \le 100{,}000$, and $w$ and $b$ are positive integers.