Welcome to Subscribe On Youtube

3949. Subtree Inversion Sum II 🔒

Description

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.

Solutions

Solution 1

All Problems

All Solutions