DMPG '18 S4 - Mimi and Prize

View as PDF

Submit solution

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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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, \ldots N, and the ith 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 \left<u,v\right> 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, \ldots 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.