# Subtree Inversion Sum
**Difficulty:** HARD
[External](https://leetcode.com/problems/subtree-inversion-sum)
Canonical: https://scaleengineer.com/dsa/problems/subtree-inversion-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Tree
---
## Problem
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.
  * Specifically, if you invert two nodes `a` and `b` such that one is an ancestor of the other (i.e., if `LCA(a, b) = a` or `LCA(a, b) = b`), then 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\],\[1,3\],\[1,4\],\[2,5\],\[2,6\]\], nums = \[4,-8,-6,3,7,-2,5\], k = 2

**Output:** 27

**Explanation:**

![](https://assets.glich.co/dsa/subtree-inversion-sum/image0.jpg)

* Apply inversion operations at nodes 0, 3, 4 and 6.
* The final `nums` array is `[-4, 8, 6, 3, 7, 2, 5]`, and the total sum is 27.

**Example 2:**

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

**Output:** 9

**Explanation:**

![](https://assets.glich.co/dsa/subtree-inversion-sum/image1.jpg)

* Apply the inversion operation at node 4.
* The final `nums` array becomes `[-1, 3, -2, 4, 5]`, and the total sum is 9.

**Example 3:**

**Input:** edges = \[\[0,1\],\[0,2\]\], nums = \[0,-1,-2\], k = 3

**Output:** 3

**Explanation:**

Apply inversion operations at nodes 1 and 2.

**Constraints:**

* `2 <= n <= 5 * 104`
* `edges.length == n - 1`
* `edges[i] = [ui, vi]`
* `0 <= ui, vi < n`
* `nums.length == n`
* `-5 * 104 <= nums[i] <= 5 * 104`
* `1 <= k <= 50`
* The input is generated such that `edges` represents a valid tree.

# Approaches
## Brute-force Backtracking
A straightforward approach is to use recursion to explore all possible valid sets of node inversions. This method, also known as backtracking, systematically tries every choice (invert or not invert) for each node and, after exploring all nodes, calculates the resulting sum. It keeps track of the maximum sum found.
**Time:** O(2^N) in the worst case. For each node, there are up to two branches of recursion. In a path-like tree, this can lead to exploring a number of paths exponential in the number of nodes `N`. · **Space:** O(N) for the recursion call stack depth in a skewed tree.
**Pros:** Conceptually simple and directly follows the problem definition.
**Cons:** Highly inefficient and will time out for the given constraints due to redundant computations.
### Explanation
We can define a recursive function, say `solve(u, p, d)`, that computes the maximum possible sum for the subtree rooted at `u`. The state for the recursion needs to carry information from the ancestors that affects decisions within the current subtree.

*   `u`: The current node being processed.
*   `p`: The parity (0 for even, 1 for odd) of inversion operations applied on the path from the root to the parent of `u`.
*   `d`: The distance to the nearest ancestor of `u` that has been inverted. We can use a special value (e.g., `k`) to signify that no ancestor has been inverted or the nearest one is at a distance of `k` or more.

For each node `u`, we explore two possibilities:
1.  **Do not invert `u`**: The node's value contributes `nums[u] * (-1)^p` to the sum. We then recursively call the function for all children of `u`, passing down the same parity `p` and an incremented distance `d+1`.
2.  **Invert `u`**: This choice is only available if the distance constraint is met, i.e., `d >= k`. If we invert `u`, its value contributes `nums[u] * (-1)^(p+1)`. For its children, the new parity becomes `(p+1)%2`, and the distance to the nearest inverted ancestor resets to `1`.

The function returns the maximum sum obtained from the valid choices. The recursion starts from the root `solve(0, 0, k)`.

Without memoization, this approach recomputes the solution for the same subproblems (same node `u` with same `p` and `d`) multiple times, leading to an exponential time complexity.
### Algorithm
1. Define a recursive function `solve(u, p, d)`.
2. Base case: If `u` is a leaf node, calculate its value based on the two choices (invert or not) and return the maximum.
3. Recursive step for an internal node `u`:
  - Calculate the sum for the 'don't invert `u`' case: `value_at_u + sum(solve(child, p, d+1))` for all children.
  - If `d >= k`, calculate the sum for the 'invert `u`' case: `inverted_value_at_u + sum(solve(child, (p+1)%2, 1))` for all children.
  - Return the maximum of the calculated sums.
4. The initial call is `solve(0, 0, k)`.

## Dynamic Programming on Tree
This approach optimizes the backtracking solution by using memoization to store and reuse the results of subproblems. The state of a subproblem is defined by the current node, the inversion parity from its ancestors, and the distance to the nearest inverted ancestor. This avoids redundant calculations and reduces the complexity significantly.
**Time:** O(N * K). Each state `(u, p, d)` is computed once. There are `N * 2 * (K+1)` such states. The work for each state is proportional to the number of its children. The total time across all states is `sum_{u,p,d} (1 + degree(u))`, which is `O(N*K)` because `sum(degree(u)) = N-1`. · **Space:** O(N * K) for the memoization table. An additional `O(N)` is used for the adjacency list and the recursion stack.
**Pros:** Efficient and guaranteed to find the optimal solution.; Handles the constraints of the problem effectively.
**Cons:** Requires more memory due to the 3D DP table.; Slightly more complex to implement than the naive backtracking approach.
### Explanation
The problem has optimal substructure and overlapping subproblems, making it suitable for dynamic programming. We define a DP state `dp[u][p][d]` which stores the maximum sum of the subtree rooted at `u` under specific ancestor conditions.

*   `u`: The current node index (`0` to `n-1`).
*   `p`: The parity of inversions from ancestors (`0` or `1`).
*   `d`: The distance to the nearest inverted ancestor (`1` to `k`). `d=k` is a special state indicating the distance is at least `k` or no ancestor is inverted.

We use a post-order traversal (DFS) to compute the DP table from leaves up to the root. For each state `(u, p, d)`, we calculate the maximum possible sum by considering two choices for node `u`:

1.  **Don't invert `u`**: The total sum is `(nums[u] * (-1)^p) + sum(dp[v][p][min(d+1, k)])` for all children `v` of `u`.
2.  **Invert `u`**: This is only possible if `d >= k`. The total sum is `(nums[u] * (-1)^(p+1)) + sum(dp[v][(p+1)%2][1])` for all children `v` of `u`.

The value `dp[u][p][d]` is the maximum of these choices. The final answer is the result of the initial call for the root node, `dp[0][0][k]`.

```java
class Solution {
    private List<List<Integer>> adj;
    private long[][][] memo;
    private int[] nums;
    private int k;

    public long subtreeInversionSum(int[][] edges, int[] nums, int k) {
        int n = nums.length;
        this.adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        // Build a directed tree (parent->child) from the undirected edges, rooted at 0
        List<List<Integer>> undirectedAdj = new ArrayList<>();
        for (int i = 0; i < n; i++) undirectedAdj.add(new ArrayList<>());
        for (int[] edge : edges) {
            undirectedAdj.get(edge[0]).add(edge[1]);
            undirectedAdj.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        visited[0] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : undirectedAdj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    adj.get(u).add(v);
                    q.add(v);
                }
            }
        }

        this.nums = nums;
        this.k = k;
        this.memo = new long[n][2][k + 1];
        for (long[][] plane : memo) {
            for (long[] row : plane) {
                Arrays.fill(row, Long.MIN_VALUE);
            }
        }

        return solve(0, 0, k);
    }

    private long solve(int u, int p, int d) {
        if (memo[u][p][d] != Long.MIN_VALUE) {
            return memo[u][p][d];
        }

        // Option 1: Don't invert node u
        long childrenSumDontInvert = 0;
        for (int v : adj.get(u)) {
            childrenSumDontInvert += solve(v, p, Math.min(d + 1, k));
        }
        long valAtU_dontInvert = (p % 2 == 0) ? nums[u] : -nums[u];
        long totalSumDontInvert = valAtU_dontInvert + childrenSumDontInvert;

        // Option 2: Invert node u
        long totalSumInvert = Long.MIN_VALUE;
        if (d >= k) {
            long childrenSumInvert = 0;
            for (int v : adj.get(u)) {
                childrenSumInvert += solve(v, 1 - p, 1);
            }
            long valAtU_invert = ((p + 1) % 2 == 0) ? nums[u] : -nums[u];
            totalSumInvert = valAtU_invert + childrenSumInvert;
        }

        return memo[u][p][d] = Math.max(totalSumDontInvert, totalSumInvert);
    }
}
```
### Algorithm
1. First, convert the given `edges` into a directed tree representation (e.g., an adjacency list where `adj[u]` contains children of `u`), rooted at 0.
2. Initialize a 3D memoization table `memo[n][2][k+1]` with a sentinel value to indicate that a state has not been computed.
3. Define a recursive function `solve(u, p, d)` that computes the maximum sum for the subtree at `u`.
4. In `solve(u, p, d)`, first check if `memo[u][p][d]` already contains a computed result. If so, return it.
5. Calculate the result for the 'don't invert `u`' case by summing `nums[u]`'s contribution and the results of recursive calls for its children: `solve(v, p, min(d+1, k))`.
6. If `d >= k`, calculate the result for the 'invert `u`' case similarly: `solve(v, 1-p, 1)`.
7. Store the maximum of the possible outcomes in `memo[u][p][d]` and return it.
8. The final answer is obtained by calling `solve(0, 0, k)`.