Minimum Cost to Color a Tree

A tree $T$ has $n$ vertices and $n - 1$ edges. The vertices are numbered from 0 to $n - 1$, and vertex 0 is the root. The edges have no weights.

Each vertex of $T$ is painted either white or black. Two adjacent vertices cannot both be black. In other words, each pair of adjacent vertices must be colored white and black, black and white, or white and white.

Each vertex has a cost for painting it white and a cost for painting 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, given as a parent vertex $p$ and a child vertex $c$, separated by a space.

Each of the next $n$ lines gives the cost of painting one vertex, starting from vertex 0 up to vertex $n - 1$. Each line contains the white cost $w$ and the black cost $b$, separated by a space.

Print the minimum cost to color every vertex of $T$ on the first line.

• $2 \le n \le 100000$
• $0 \le p, c \le n - 1$, $p \ne c$
• The graph formed by the edges is a tree.
• $1 \le w, b \le 100000$, and $w$ and $b$ are positive integers.