Minimum Operations to Blacken a Tree

You are given a tree with n nodes rooted at 1. Each node u has an initial color given by \(\mathrm{color}_u\) which is either black (denoted 0) or white (denoted 1). You are allowed two types of operations:

• Operation 1: Choose any node \(u\) and flip the color of every node on the simple path from \(u\) to the root (both endpoints included). In other words, for every node on that path, black becomes white and white becomes black.
• Operation 2: Choose any node \(u\) and flip the color of every node in the subtree of \(u\) (including \(u\) itself).

Your goal is to make every node black using as few operations as possible. Note that the operations are commutative modulo 2 (flipping twice is the identity) so you can view the operations as adding 1 modulo 2 on the appropriate sets.

In mathematical form, if we denote by \(x_u\) the indicator of applying Operation 1 at node \(u\), and \(y_u\) the indicator of applying Operation 2 at node \(u\), then the final color of a node \(v\) will be

[ \mathrm{final}v = \mathrm{color}v \oplus \Bigl( \bigoplus{\substack{u;:; v \text{ is on the path from } u \text{ to } 1}} x_u \Bigr) \oplus \Bigl( \bigoplus{\substack{u;:; u \text{ is an ancestor of } v}} y_u \Bigr) = 0. ]

You need to choose the sets \(\{x_u\}\) and \(\{y_u\}\) (each either 0 or 1) such that the above holds for every node \(v\) and \(\sum_{u=1}^{n}(x_u+y_u)\) is minimized.

Input Format: The input begins with an integer n. Then n-1 lines follow; each contains two integers \(u\) and \(v\) indicating an edge between nodes \(u\) and \(v\). The last line contains n space‐separated integers: \(\mathrm{color}_1, \mathrm{color}_2, \dots, \mathrm{color}_n\) (each 0 or 1), describing the initial colors.

Output Format: Output a single integer — the minimum number of operations required to make the entire tree black.

Note: All formulas in this statement are rendered in \(\LaTeX\) format.

inputFormat

The first line contains an integer n (the number of nodes).

Each of the next n-1 lines contains two integers u and v representing an edge in the tree.

The last line contains n space‐separated integers: \(\mathrm{color}_1, \mathrm{color}_2, \dots, \mathrm{color}_n\) (each either 0 or 1) representing the initial colors (0 for black, 1 for white).

outputFormat

Output a single integer: the minimum number of operations required so that all nodes become black.

sample

2
1 2
1 1

1