DMPG '18 S4 - Mimi and Prize

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types

A tree is a connected graph with N nodes and N-1 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 1, 2, \dots, N, and the i^\text{th} node has a value, A_i. 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 \langle u,v \rangle such that the values on the path match the parity of the index. Specifically, if you took the path starting from u and ending at v and wrote it into an array with A_u as the first element and A_v as the last, then the j^\text{th} value of this array must be congruent to j \bmod 2, for every j from 1 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:

1 \le A_i \le 10^9

Subtask 1 [10%]

1 \le N \le 500

Subtask 2 [10%]

1 \le N \le 2\,000

Subtask 3 [80%]

1 \le N \le 200\,000

Input Specification

The first line of input will contain N, the number of nodes in the tree.
The next line of input will contain N space separated integers, A_1, A_2, \dots, A_N.
The next N-1 lines of input will each contain a pair of integers, a_i\ b_i, indicating that there is an edge between a_i and b_i.

Output Specification

A single integer, the number of ordered pairs which satisfy the given condition.

Sample Input

1 2 3 4
1 2
2 3
3 4

Sample Output



There are no comments at the moment.