A tree is a connected graph with nodes and edges. An interesting property of trees is that there exists exactly 1 path between any two nodes.
As the top CS student in her year, Mimi's ICS teacher awards her a tree at graduation. The tree's nodes are labelled , and the node has a value, . However, having scored only half a percentage point lower than her, you decide to contest this prize!
The teacher arranges a code-off on this tree: you are to determine the number of ordered pairs such that the values on the path match the parity of the index. Specifically, if you took the path starting from and ending at and wrote it into an array with as the first element and as the last, then the value of this array must be congruent to , for every from to the size of the array. Note that this array is 1-indexed.
Can you solve this problem and claim the title of top ICS student?
For all subtasks:
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [80%]
The first line of input will contain , the number of nodes in the tree.
The next line of input will contain space separated integers, .
The next lines of input will each contain a pair of integers, , indicating that there is an edge between and .
A single integer, the number of ordered pairs which satisfy the given condition.
4 1 2 3 4 1 2 2 3 3 4