Xor operation, dfs.
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.
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.
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 eq 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 eq 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.