XOR of Two Disjoint Subtrees

Hard

You get a tree of n nodes numbered 0 to n - 1, rooted at node 0. The edges come as a list edges, where a pair [a, b] joins nodes a and b. Each node has a weight weights[i]. The subtree of a node is the node itself together with all its descendants. Choose two subtrees that share no node, sum the weights in each, and take the bitwise XOR of the two sums. Return the largest value you can get. If no two disjoint subtrees exist, return 0.

Example 1

n=5, edges=[[0, 1], [0, 2], [2, 3], [2, 4]], weights=[1, 9, 4, 2, 3] → 11

Node 1's subtree sums to 9 and node 2's to 4 + 2 + 3 = 9, but 9 XOR 9 = 0. Nodes 1 and 3 give 9 XOR 2 = 11, nodes 1 and 4 give 9 XOR 3 = 10. The answer is 11.

Example 2

n=4, edges=[[0, 1], [1, 2], [2, 3]], weights=[5, 5, 5, 5] → 0

The tree is a chain, so any two subtrees are nested and the answer is 0.

Example 3

n=3, edges=[[1, 0], [0, 2]], weights=[10, 6, 1] → 7

Constraints

2 ≤ n ≤ 5 · 10⁴
len(edges) = n - 1, 0 ≤ a, b < n
len(weights) = n
1 ≤ weights[i] ≤ 10⁹
The edges form a tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Graph Trie

Similar problems

Distance Totals in a Road Tree Hard A Beetle Wandering a Tree Hard Tree Path Without Twin Neighbours Hard Discounted Trips Through a Tree Hard Joining Two Trees Hard

Input

n=5, edges=[[0, 1], [0, 2], [2, 3], [2, 4]], weights=[1, 9, 4, 2, 3]

Expected

Run checks the first 3 tests in your browser. Submit checks all 74 tests on the server, hidden ones included.