Skip to main content
Talentd

Subtree Inversion Sum II - Solution & Explanation

HardPremiumFree on FleetCode5 min read
Practice this problem

Problem Statement

You are given an undirected tree rooted at node 0, with n nodes numbered from 0 to n - 1. The tree is represented by a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates an edge between nodes ui and vi.

You are also given an integer array nums of length n, where nums[i] represents the value at node i, and an integer k.

You may perform inversion operations on a subset of nodes subject to the following rules:

  • Subtree Inversion Operation:

    • When you invert a node, every value in the subtree rooted at that node is multiplied by -1.

  • Distance Constraint on Inversions:

    • You may only invert a node if it is “sufficiently far” from any other inverted node.

    • If you invert two nodes a and b, the distance (the number of edges on the unique path between them) must be at least k.

Return the maximum possible sum of the tree’s node values after applying inversion operations.

 

Example 1:

Input: edges = [[0,1],[0,2],[0,3],[1,4],[1,5]], nums = [1,0,-10,3,4,5], k = 2

Output: 23

Explanation:

After inverting the subtree rooted at node 2, the maximum sum becomes 1 + 0 + 10 + 3 + 4 + 5 = 23.

Example 2:

Input: edges = [[0,1],[1,2]], nums = [5,-10,-10], k = 1

Output: 25

Explanation:

After inverting the subtree rooted at node 1, the maximum sum becomes 5 + 10 + 10 = 25.

Example 3:

Input: edges = [[0,1],[0,2]], nums = [1,-5,-6], k = 2

Output: 12

Explanation:

  • After inverting the subtrees rooted at nodes 1 and 2, nums = [1, 5, 6].
  • This is valid because nodes 1 and 2 are two edges apart (1 → 0 and 0 → 2), which is at least k.
  • The maximum sum is 1 + 5 + 6 = 12.

Example 4:

Input: edges = [[0,1],[0,2]], nums = [1,-5,-6], k = 3

Output: 10

Explanation:

  • After inverting the subtree rooted at nodes 0, nums = [-1, 5, 6].
  • The maximum sum is (-1) + 5 + 6 = 10.
  • Note that we cannot invert nodes 1 and 2 because their distance is 2 < k = 3.

 

Constraints:

  • nums.length == n
  • edges.length == n - 1
  • 2 <= n <= 5 * 104
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] < n
  • -4 * 104 <= nums[i] <= 4 * 104
  • 1 <= k <= 50
  • It is guaranteed that edges forms a tree.

Approach Overview

Problem Overview: You are given a tree where each node has a value. For every node, consider the values inside its subtree and count inversion pairs (i, j) where i appears before j but value[i] > value[j]. The task is to efficiently compute the inversion contribution across all subtrees without recomputing from scratch for each node.

Approach 1: Recompute Inversions Per Subtree (Brute Force) (O(n^2 log n) time, O(n) space)

Traverse the tree with DFS. For each node, collect all values from its subtree into an array. Run a classic inversion counting algorithm using merge sort on that array. Merge sort counts inversions in O(k log k) for a subtree of size k. Since many subtrees overlap and nodes may be processed repeatedly, the total runtime grows toward O(n^2 log n). This method is straightforward and useful for validating correctness on small inputs but does not scale to large trees.

Approach 2: DFS + Small-to-Large Set Merging (DSU on Tree) (O(n log n) time, O(n) space)

Process the tree using postorder DFS. Each node maintains a balanced structure (such as a multiset or Fenwick-friendly ordered container) storing values from its subtree. While returning from recursion, merge child containers into the largest one using the small-to-large technique. When inserting elements from the smaller container, query how many existing values are greater to count new inversion pairs. Because each element moves containers only logarithmically many times, the total complexity becomes O(n log n). This pattern is commonly called DSU on tree and appears frequently in advanced tree problems.

Approach 3: Euler Tour + Fenwick Tree (O(n log n) time, O(n) space)

Flatten the tree using an Euler tour so every subtree becomes a contiguous range in an array. After coordinate-compressing values, process nodes while maintaining a Fenwick Tree or Binary Indexed Tree. As nodes enter the structure, query the number of previously inserted values greater than the current one to accumulate inversion counts. Range boundaries from the Euler tour allow subtree queries to be handled efficiently. This approach replaces explicit set merging with prefix-sum queries and updates.

Recommended for interviews: Interviewers usually expect the small-to-large merging (DSU on tree) approach or an Euler tour combined with a Fenwick Tree. The brute-force solution demonstrates understanding of inversion counting with merge sort, but the optimized O(n log n) solution shows you can combine DFS, subtree processing, and ordered data structures to eliminate repeated work.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recompute inversions per subtree (merge sort)O(n^2 log n)O(n)Conceptual baseline or small constraints
DFS with small-to-large merging (DSU on tree)O(n log n)O(n)General optimal solution for subtree aggregation
Euler tour + Fenwick TreeO(n log n)O(n)When subtree ranges can be flattened into array intervals

Frequently Asked Questions

Is Subtree Inversion Sum II easy or hard?
Subtree Inversion Sum II is considered a hard problem because it combines multiple advanced ideas: tree traversal, inversion counting, and efficient data structure merging. Recognizing that naive subtree recomputation is too slow and switching to DSU-on-tree or Fenwick-based aggregation is the key difficulty.
Subtree Inversion Sum II Python/Java solution
Python implementations usually use coordinate compression with a Fenwick Tree or the small-to-large merging technique using sorted containers. Java solutions often rely on TreeMap, Fenwick Tree arrays, or custom DSU-on-tree implementations. All optimal versions run in O(n log n) time.
How to solve Subtree Inversion Sum II in O(n log n)?
Perform a DFS over the tree and maintain a structure storing values from the processed subtree. Using small-to-large merging ensures each element is moved only a limited number of times. When inserting a value, query how many existing values are greater using a balanced BST or Fenwick Tree, which counts new inversion pairs in logarithmic time.
What is the best approach for Subtree Inversion Sum II?
The most practical solution uses DFS with small-to-large merging (DSU on tree). Each subtree maintains an ordered structure of values, and smaller child structures are merged into the largest one while counting how many existing values create inversions. This reduces repeated work and achieves O(n log n) time with O(n) space.
Is Subtree Inversion Sum II asked at Google/Amazon/Meta?
Problems combining subtree processing, inversion counting, and ordered data structures are common in interviews at companies like Google, Amazon, and Meta. Variants appear as tree queries, DSU-on-tree tasks, or Fenwick Tree applications where candidates must aggregate subtree statistics efficiently.
What data structure is used in Subtree Inversion Sum II?
Typical solutions rely on ordered structures such as a multiset, balanced binary search tree, or Fenwick Tree after coordinate compression. These structures allow fast insertion and queries for how many values are greater or smaller, which is essential for counting inversion pairs.
What is the time complexity of Subtree Inversion Sum II?
The optimal solutions run in O(n log n) time. Techniques such as DSU on tree or Euler tour combined with a Fenwick Tree allow each node value to be inserted and queried logarithmically. A naive approach that recomputes inversion counts for every subtree can degrade to O(n^2 log n).

Ready to solve this problem?

Practice Subtree Inversion Sum II with our built-in code editor and test cases.

Practice on FleetCode