Minimum Toggle Operations on a Tree

You are given a tree with N nodes. Each node i has a binary weight \(a_i\) (either 0 or 1). You are allowed to perform a toggle operation on any node. Toggling a node i will flip the weight of node i as well as the weights of all nodes that are directly connected to it (i.e. its neighbors in the tree).

Your task is to determine the minimum number of toggle operations required so that the weight of every node becomes 0.

The effect of a toggle operation on node \(i\) can be described mathematically. If \(x_i\) is a binary variable (0 meaning no toggle, 1 meaning toggle) for node \(i\), then for every node \(i\) the final weight will be

[ a_i + x_i + \sum_{j\in N(i)} x_j \equiv 0 ; (\bmod; 2), ]

where \(N(i)\) represents the set of nodes directly adjacent to node \(i\). The goal is to choose \(x_i \in \{0,1\}\) for every node \(i\) so that all equations are satisfied while minimizing \(\sum_{i=1}^{N} x_i\).

inputFormat

The first line contains a single integer \(N\), the number of nodes in the tree. The second line contains \(N\) space-separated integers \(a_1, a_2, \dots, a_N\), where each \(a_i \in \{0,1\}\) denotes the weight of node \(i\). Each of the following \(N-1\) lines contains two integers \(u\) and \(v\) indicating that there is an edge between nodes \(u\) and \(v\). The nodes are numbered from 1 to \(N\).

outputFormat

Output a single integer, the minimum number of toggle operations required to make every node's weight 0. If no solution exists then output -1.

sample

1
0

0