PROBLEM LINK:Author: Yuri Shilyaev DIFFICULTY:Easymedium. 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 onebits 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 onebits $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 onebits 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.
This question is marked "community wiki".
asked 20 May, 16:17
showing 5 of 6
show all

This is the best explanation of this problem I think. Courtesy: Silence_ for_Melody (CF) I will give you the theory behind and you have to figure it out, sorry for my English since now. You must know some properties about trees and XOR operation.
For one moment forget about ages in the problem and try to solve the following: How many pairs of cities are so their distance is even? How many there are so their distance is odd? Now forget about the distance on work over ages. How many pairs of cities there are so the bits in their XOR are even? How many there are so the bits in their XOR are odd? Last, and what makes this problem awesome, observation: When you want to evaluate parity of bits in the XOR of A and B, does the order of bit in A and B matter? Just think about it. Hope everything is clear answered 21 May, 19:51

I feel this problem deserves more explanation :( Like,  "Let's use the fact that parity of the number of onebits $a_u \oplus a_v$ will not change if we replace $a_u$ with parity of one bits in $a_u$." What does this mean? Are you intending to say that we are replacing $a_u$ with "Parity of $1's$ in $a_u$" ? If yes, then why does this work? Do you have a proof of correctness, or is it some random observation we had to make? I agree that strong practice gives you a killer instinct of making observations, but a formal proof and explanation helps newbies to learn that thing and grasp the concept. I hope you understand what I am trying to convey :) . answered 21 May, 18:59
Yes I read the editorial twice but did not get it. Then I thought it's just me and may be I am not smart enough. In my opinion, CHEFLAKE also needs a better explanation.
(21 May, 19:02)
"The proof is left as an exercise for the reader" :P Also @sorb1997, always feel free to ask if you have a doubt. It is quite likely someone will answer.
(21 May, 19:46)
1
There was a nice come back to it in past. Lemme copy it
I believe yes, its good to leave exercises for readers, but if I were there, I'd at least give some hints or the answer in my bonus part of editorial :3 IDK as an editorialist I feel restless elsewise XD
(21 May, 20:16)

Root the tree at 1 and run simple dfs to calculate dept of each node let $x[i]$ be number set bits in $a[i] \oplus a[1]$ now we divide all nodes 2 catogories 1) where parity of $dept[i]$ and $x[i]$ is same  $c1$ 2) where parity of $dept[i]$ and $x[i]$ is is different  $c2$ consider a node of $c2$, right now with $a1$ he has parity of distance and difference in bits, as different and he wants that to remain the same, So he wants to be paired with someone who has either a) parity of $dept[i]$ and $x[i]$ both are 0. pairing with them will not any effect on overall parity b) parity of $dept[i]$ and $x[i]$ both are 1, pairing with them will result with inverting the parity of both ($dept[i]$ and $x[i]$), but since in a node of $c2$ it was different before, it will different after pairing also. Clearly, both are attributes of nodes of $c1$ . Hence every node of c2 can be paired with c1. So the answer is simply $c1*c2$ Solution link answered 25 May, 13:57

@hloga_ygrt Can you please state clearly, where under the problem is the definition of parity mentioned. I'm sorry I'm not able to find it. answered 21 May, 17:49

@hloga_ygrt, yeah i also can't seem to find the definition of parity anywhere below the question. answered 21 May, 19:12

From Editorial : bu⊕bv⊕du⊕dv=1 . Can we proceed further in this way ?  bu and du is known and so are bv and dv. now store bi⊕di for each i and count the number of ones (cnt1) and zeros (cnt0) in the array thus formed. and the answer is (cnt0*cnt1) ?? answered 26 May, 13:00

what does in particular "parity" mean? I am even having trouble understanding problem statement due to this.
It was commented under the problem that parity is $1$ or $0$, is the number even or odd.
A nice problem that resolves to a simple solution :)
However it is worth mentioning that both author and tester solutions here use a slightly different approach than the one described in the editorial, in case someone gets confused.
Nice question! Any similar questions available on any platform?
Explanation about parity is given neither in problem nor in comments under the problem and although setter commented but still i don't get it what is parity implying here? "parity of number of one bits", "parity of shortest path" what does these clauses imply???
@divik544 you can consider parity of x as x mod 2. Wiki page: parity