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:
- Pick a node r and make it the root of the tree.
- In the new tree, pick a node x, and for each node v in the subtree of x, update A[v] = A[v] XOR K.
Task
Determine the maximum sum of values of all the nodes in the tree that can be obtained.
Notes
- 1-Based indexing.
- XOR denotes the Bitwise XOR operator.
- A subtree of a node contains all the nodes that are descendants of that node and the node itself.
Example
Assumptions
- N = 3
- edges = [(1, 2), (1, 3)]
- A = [1, 1, 3]
- K = 3
Answer
- The maximum sum is 7.
N can be up to 10^5.
How do we do indp and outdp calculations here?
My solution