Google OA 2024 - Subtree XOR

You are given the following:

• A tree with N nodes
• An array A denoting the value of each node
• A non-negative integer K

You can do the following operation on the tree at most once:

1. Pick a node r and make it the root of the tree.

2. In the new tree, pick a node x and for each of the nodes in the subtree of x, update A[subtree] = A[subtree] ^ K.

Task:

Determine the maximum sum of values of all the nodes in the tree that can be obtained.

Notes:

• 1-Based indexing.
• ^ denotes the Bitwise-XOR operator.
• A subtree of a node contains all the nodes that are descendants of that node and the node itself.

Input Format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains T denoting the number of test cases. T also specifies the number of times you have to run the maximum sum function on a different set of inputs.
• For each test case:
• The first line contains an integer N denoting the number of nodes.
• Each of the following (N-1) lines contains two space-separated integers denoting an edge between the given nodes.
• The next line contains N space-separated integers denoting the value of nodes.
• The next line contains a single integer K.

Example

N = 3
edges = {(1, 2), (1, 3)}
A = [1, 1, 3]
K = 3

Approach:

You perform the following operation to get the maximum sum:

• r = 3 as the root of the tree.
• Update the value in the subtree of x = 1
• The new array becomes A = [2, 2, 3]

The sum obtained is 2+2+3 = 7 which is maximum. Hence, the answer is 7.