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 7th 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.
1 ≤ t ≤ 11
1 ≤ n ≤ 105
1 ≤ A[i] ≤ 100000
1 ≤ B[i] ≤ 100000
- 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 ui and vi (1 ≤ ui, vi ≤ n ; ui ≠ vi) meaning there is an edge between nodes ui and vi.
- Next line has n space-separated integers A1, A2, A3 ,….. An denoting the initial value of nodes.
- Next line has n space-separated integers B1, B2, B3 ,….. Bn denoting the final values of nodes.
Output the minimum number of operations required and the sum of values added or subtracted in these operations.
9 3 5 6 2 3 8 10
9 3 3 5 2 1 8 10Output:
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 1st 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 2nd 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 3rd operation: 9 3 3 5 2 1 8 10
Sum of values added/subtracted = -2-1+1 = -2
Let f(x) = (number of set bits in x) mod 2.
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.