Sofdor Ali loves Computer Science. He prefers hexadecimal number system to decimals, just because it would be easier to represent hexadecimal numbers in the computer. Since Sofdor loves Computer Science, inevitably he has fallen in love with Graph Theory. Lately, he has gone through many books on Graph Theory and solved many exercise problems in the process. He shared one of these problems with his friend, Mr. Iqbal. Here is the problem:
You are given a connected rooted tree, where each node is colored either black or white. You can perform one flip operation in the tree. In a flip operation, one can choose one node X of the tree, and flip it's color and all the colors of each of the nodes in X's sub-tree. That is, after one flip, all the white nodes in X's sub-tree become black and all the black nodes become white. Same goes for X as well, if it's black, it becomes white and so on.
Now you have tell us that after exactly one flip operation in the tree, what would be the maximum number of white nodes?
Input starts with an integer N (1 ≤ N ≤ 100000), indicating the number of nodes in the tree. After that, there are N integers indicating the initial color of the nodes. If the i'th node is white, then the i'th number is 1, otherwise it's 0.
The next N−1 lines each contains two integers u and v indicating an edge between u and v (0 ≤ u,v ≤ N). The root of the tree is always 0.
For 50% of the cases, N will not exceed 100.
Print on single line, an integer, the maximum number of white nodes that can be achieved after exactly one flip.
| Input | Output |
|---|---|
10 0 1 0 0 1 1 0 1 0 0 0 4 0 1 1 7 0 5 5 8 8 6 1 9 8 2 6 3 | 8 |
A tree is called a rooted tree, when one specific node is always considered as the root node.
In a connected tree, every pair of nodes is connected with a path.