Xorrrr

5

6 votes
Depth First Search, Graphs, Algorithms
Problem

Bob lives in a country called HackerLand and in this country, there are \(N\) cities numbered \(1 \) to \(N\) and they form a tree. That is, there are \(N - 1\) undirected roads between these \(N\) cities and every two cities can reach each other through these roads. The length of the road between city \(i\) and city \(j\) is \((i + j)\) (meaning if there is a road between city \(i\) and city \(j\) then the length will be \(i + j\)).

So a great scientist in HackerLand invented the new car in which Bob can travel from one city to another city in \(f(i, j)\) time where \(f(i, j)\) indicates bitwise xor of length of the roads in the simple path between city \(i\) and \(j\). So Bob was curious to find the bitwise xor of all \(f(i, j)\) such that  \(1 \leq i \lt j \leq N \). Help Bob to find.

For example, if our country has \(4\) cities then we have to find  \( f(1,2) ⊕ f(1,3) ⊕ f(1,4) ⊕ f(2,3) ⊕ f(2,4) ⊕ f(3,4)\) where \(\oplus\) denotes bitwise xor operator.

Input Format

  • The first line contains \(N\), the number of cities in the country.
  • Then \(N - 1\) lines contains two integers \(u\) and \(v\), means that there is a undirected road between city \(u\) and city \(v\). It is guaranteed that the given roads form a tree.

Output Format

Print a single integer denoting our answer

Constraints

\(1 \leq N \leq 10^5 \\ 1 \leq u, v \leq N\)

Note: The country HackerLand has a tree structure

Time Limit: 2
Memory Limit: 512
Source Limit:
Explanation

For the given tree in the sample
\(f(1,2) = 3, f(1,3) = 6, f(1,4) = 5, f(1,5) = 14 \\ f(1,6) = 11, f(2,3) = 5, f(2,4) = 6, f(2,5) = 13 \\ f(2,6)=8, f(3,4) = 3, f(3,5) = 8, f(3,6)=13 \\ f(4,5) = 11, f(4,6) = 14, f(5,6)=5\)

If we xor all of them we will get a \(5\).

Editor Image

?