### PROBLEM LINK:

**Author:** Yuri Shilyaev

**Tester:** Hasan Jaddouh

**Editorialist:** Yury Shilyaev

### DIFFICULTY:

Easy-medium.

### PREREQUISITES:

Xor operation, dfs.

### PROBLEM:

You are given a tree with N vertices and N - 1 edge. Each vertex i has a value a_i associated with it. You have to count the number of unordered pairs (u, v), that the parity of the number of one-bits in a_u \oplus a_v is not equal to the parity of the shortest path between u and v.

### QUICK EXPLANATION:

Let’s use the fact that parity of the number of one-bits a_u \oplus a_v will not change if we replace a_u with parity of one bits in a_u.

### EXPLANATION:

Let |x| be the number of one-bits in binary representation of x, dist(u, v) be the length of the shortest path between u and v, and x\ \%\ 2 be the remainder of the division x by two.

It is easy to prove the fact, that |a_u \oplus a_v|\ \%\ 2 = (|a_u|\ \%\ 2) \oplus (|a_v|\ \%\ 2). To use it, let’s transform b_i = |a_i|\ \%\ 2.

Now the task is the following: count the number of pairs (u, v), that b_u \oplus b_v \neq dist(u, v)\ \%\ 2. If we had rooted our tree, calculated for each v it’s dist(root, v) (the number of edges in the path from the root), then:

dist(u, v)\ \%\ 2 = (dist(root, u)\ \%\ 2) \oplus (dist(root, v)\ \%\ 2).

That’s why we apply transform d_i = dist(root, i) \ \%\ 2 for array d and reduce a problem to an easy one: count the number of pairs (u, v), such that b_u \oplus b_v \neq d_u \oplus d_v.

By transfering everything to the left we achieve:

b_u \oplus b_v \oplus d_u \oplus d_v = 1

Easy problem, right? Let’s just calc cnt[bvalue][dvalue] - number of vertices with b_u = bvalue and d_u = dvalue, and iterate all possible pairs of bvalue and dvalue that give xor 1, and add cnt[bvalue_u][dvalue_u] \cdot cnt[bvalue_v][dvalue_v] to the answer.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.