Difficult Choice

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef and his mother are going travelling. Chef's world consists of $N$ cities (numbered $1$ through $N$) connected by $N1$ bidirectional roads such that each city can be reached from any other city using roads. For each city, we know its age — the number of years elapsed since the foundation of the city; let's denote the age of city $i$ by $a_i$. First of all, Chef and his mother have to decide what city they should visit first. Suppose that Chef chooses a city $c_c$ and his mother chooses a (not necessarily different) city $c_m$. The *difference* of their choices is the number of different bits in the binary representations of $a_{c_c}$ and $a_{c_m}$. Chef will not argue with his mother if the parity of this difference is not equal to the parity of the length of the shortest path between cities $c_c$ and $c_m$ (the number of roads on the shortest path between them). Find the number of ways to choose the cities $c_c$ and $c_m$ such that Chef avoids quarreling with his mother. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  Each of the following $N1$ lines contains two spaceseparated integers $A$ and $B$ denoting a road between cities $A$ and $B$.  The last line contains $N$ spaceseparated integers $a_1, a_2, \dots, a_N$. ### Output For each test case, print a single line containing one integer — the number of valid pairs $c_c, c_m$. ### Constraints  $1 \le T \le 10$  $1 \le N \le 10^5$  $1 \le A, B \le N$  $0 \le a_i \le 10^9$ for each valid $i$ ### Sample Input ``` 1 3 1 2 1 3 1 2 3 ``` ### Sample Output ``` 2 ``` ### Explanation **Example case 1:** The two possible choices are $c_c=2, c_m=3$ (their binary representations differ by one bit, the shortest path has length $2$) and $c_c=1, c_m=2$ (there are two different bits in their binary representations and the shortest path has length $1$).Author:  hloya_ygrt 
Editorial  https://discuss.codechef.com/problems/CHEFTRVL 
Tags  cook94, hloya_ygrt, xor 
Date Added:  9052018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 