SE7EN  Seven
David Mills and William Somerset have teamed up again to catch a criminal. This criminal is a bit different from others, he challenges the detectives by leaving a puzzle at the crime scene which is the clue to his next crime. Both the detectives work hard to crack the puzzle, but the criminal is always one step ahead. For his 7^{th} and last crime, he left a problem for the detectives. David wants your help for this one to catch the criminal.
The criminal gave you a tree having n nodes with 1 as the root. Each node is numbered from 1 to n. Every node has a value represented by the array A.
You are given another array B. You have to convert the node values from A to B by performing the minimum number of operations. In one operation you can select any node i and add or subtract any value. And the same value will get added to or subtracted from the special node in the subtree of the node i.
Special node q in the subtree of p is defined as node such that:
(Number of set bits in p) mod 2 = (Number of set bits in q) mod 2
You have to tell the minimum operations to convert node values from A to B and the sum of values added or subtracted in these operations.
CONSTRAINTS:
1 ≤ t ≤ 11
1 ≤ n ≤ 10^{5}
1 ≤ A[i] ≤ 100000
1 ≤ B[i] ≤ 100000
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 denoting the number of nodes.
 Each of the next n  1 lines contains two integers u_{i} and v_{i }(1 ≤ u_{i}, v_{i} ≤ n ; u_{i} ≠ v_{i}) meaning there is an edge between nodes u_{i} and v_{i}.
 Next line has n spaceseparated integers A_{1}, A_{2}, A_{3 },….. A_{n} denoting the initial value of nodes.
 Next line has n spaceseparated integers B_{1}, B_{2}, B_{3 },….. B_{n} denoting the final values of nodes.
OUTPUT:
Output the minimum number of operations required and the sum of values added or subtracted in these operations.
Example
Input:1
8
1 3
3 2
3 7
6 2
4 1
8 4
4 5
9 3 5 6 2 3 8 10
9 3 3 5 2 1 8 10
Output:3 2
Explanation:
You can select node 3 with value 5 and subtract 2, it will also get subtracted from the special node 6 in its subtree.
Values after 1^{st} operation: 9 3 3 6 2 1 8 10
Now select node 4 with value 6 and subtract 1, it will also get subtracted from the special node 8 in its subtree.
Values after 2^{nd} operation: 9 3 3 5 2 1 8 9
Now select node 8 and add 1. There is no special node in its subtree.
Values after 3^{rd} operation: 9 3 3 5 2 1 8 10
Sum of values added/subtracted = 21+1 = 2
hide comments
hodobox:
20190102 00:54:21
Let f(x) = (number of set bits in x) mod 2.


gangacool:
20180728 18:39:47
In one operation you can select any node i and add or subtract any value. And the same value will get added to or subtracted from the special node in the subtree of the node i.

Added by:  ak07 
Date:  20180706 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own 