Google OA-9 2024
Problem Description
You are given the following:
- A tree with N nodes.
- An array A that represents the value of each node.
- A non-negative integer K.
You are allowed to perform the following operation at most once:
- Select a node r and make it the new root of the tree.
- In this modified tree, choose a node x and update the values of all nodes in the subtree of x using the operation A[subtree] = A[subtree] ^ K.
Task:
Determine the maximum possible sum of values of all the nodes in the tree after performing the allowed operations.
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.