Maximum XOR of Two Non-Overlapping Subtrees

Maximum XOR of Two Non-Overlapping Subtrees - Problem

There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

The root of the tree is the node labeled 0. Each node has an associated value. You are given an array values of length n, where values[i] is the value of the ith node.

Select any two non-overlapping subtrees. Your score is the bitwise XOR of the sum of the values within those subtrees.

Return the maximum possible score you can achieve. If it is impossible to find two non-overlapping subtrees, return 0.

Note that:

The subtree of a node is the tree consisting of that node and all of its descendants.
Two subtrees are non-overlapping if they do not share any common node.

Input & Output

Example 1 — Basic Tree

$ Input: n = 6, edges = [[0,1],[1,3],[1,4],[0,2],[2,5]], values = [2,8,3,6,2,5]

› Output: 24

💡 Note: We can select subtree rooted at node 1 (sum = 8+6+2 = 16) and subtree rooted at node 2 (sum = 3+5 = 8). XOR: 16 ⊕ 8 = 24

Example 2 — Small Tree

$ Input: n = 3, edges = [[0,1],[0,2]], values = [4,3,1]

› Output: 0

💡 Note: Any two non-overlapping subtrees would be single nodes. Maximum XOR is 3 ⊕ 1 = 2, but since we need subtrees, best is 0

Example 3 — Linear Tree

$ Input: n = 4, edges = [[0,1],[1,2],[2,3]], values = [1,1,1,1]

› Output: 3

💡 Note: Select subtree at node 0 (sum=1) and subtree at node 3 (sum=1). But better: node 1 subtree (sum=3) and node 3 (sum=1). XOR: 3 ⊕ 1 = 2. Actually, best is subtree [0,1,2] = 3 and node 3 = 1, giving 3 ⊕ 1 = 2. Wait, let me recalculate: we can have subtree starting at 1 (includes 2,3) = 3, and node 0 = 1, giving 3 ⊕ 1 = 2. Or subtree at 0 (includes 1,2,3) = 4 but then no second subtree. Best is subtree 1,2 = 2 and subtree 3 = 1, giving 2 ⊕ 1 = 3

Constraints

2 ≤ n ≤ 5 × 10⁴
edges.length == n - 1
0 ≤ ai, bi < n
ai ≠ bi
1 ≤ values[i] ≤ 10⁹
The given edges form a valid tree

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with node values and edges

Find Subtrees

Identify all possible non-overlapping subtree pairs

Maximum XOR

Calculate XOR of subtree sums and find maximum

Key Takeaway

🎯 Key Insight: Use DFS to generate all subtree sums, then find maximum XOR efficiently with Trie

Asked in

G Google 12 a Amazon 8 M Microsoft 6

This tree problem requires finding two non-overlapping subtrees with maximum XOR of their sums. The key insight is to use DFS to generate all possible subtree sums, then efficiently find the maximum XOR using a Trie data structure. Best approach: DFS + Trie with Time: O(n log V), Space: O(n log V).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - All Subtree Pairs	O(n²)	O(n)	Generate all possible subtree sums, then check every pair for maximum XOR
DFS + Trie Optimization	O(n * log V)	O(n * log V)	Use DFS to collect subtree sums, then use Trie to efficiently find maximum XOR

Brute Force - All Subtree Pairs — Algorithm Steps

Build adjacency list from edges
DFS to find all subtree sums
Check all pairs of subtrees for non-overlap
Calculate XOR for each valid pair

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Tree

Create adjacency list from edges

DFS Traversal

Calculate all subtree sums

Check Pairs

Find maximum XOR between any two sums

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 1000

long long subtreeSums[MAX_N];
bool visited[MAX_N];
int subtreeCount = 0;

long long dfs(int node, int parent, int adj[MAX_N][MAX_N], int adjCount[MAX_N], int* values) {
    visited[node] = true;
    long long currentSum = values[node];
    
    for (int i = 0; i < adjCount[node]; i++) {
        int neighbor = adj[node][i];
        if (neighbor != parent && !visited[neighbor]) {
            currentSum += dfs(neighbor, node, adj, adjCount, values);
        }
    }
    
    subtreeSums[subtreeCount++] = currentSum;
    return currentSum;
}

long long solution(int n, int edges[][2], int edgeCount, int* values) {
    if (n < 2) return 0;
    
    int adj[MAX_N][MAX_N];
    int adjCount[MAX_N] = {0};
    
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0], v = edges[i][1];
        adj[u][adjCount[u]++] = v;
        adj[v][adjCount[v]++] = u;
    }
    
    subtreeCount = 0;
    memset(visited, false, sizeof(visited));
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, -1, adj, adjCount, values);
        }
    }
    
    long long maxXor = 0;
    for (int i = 0; i < subtreeCount; i++) {
        for (int j = i + 1; j < subtreeCount; j++) {
            long long xorVal = subtreeSums[i] ^ subtreeSums[j];
            if (xorVal > maxXor) {
                maxXor = xorVal;
            }
        }
    }
    
    return maxXor;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simple parsing for demo - in practice would need proper JSON parsing
    int edges[MAX_N][2];
    int values[MAX_N];
    int edgeCount = n - 1;
    
    // Read edges and values (simplified)
    for (int i = 0; i < edgeCount; i++) {
        scanf("%d %d", &edges[i][0], &edges[i][1]);
    }
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &values[i]);
    }
    
    printf("%lld\n", solution(n, edges, edgeCount, values));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

DFS takes O(n) time, but checking all pairs of subtrees takes O(n²)

⚠ Quadratic Growth

Space Complexity

O(n)

Storing adjacency list and subtree sums requires O(n) space

⚡ Linearithmic Space

8.9K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - All Subtree Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler