3544. Subtree Inversion Sum
Hard
50 Points
Array
Dynamic Programming
Tree
Depth-First Search
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:
Return the maximum possible sum of the tree's node values after applying inversion operations.
Examples
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:
Example 2
Input: edges = [[0,1],[1,2],[2,3],[3,4]], nums = [-1,3,-2,4,-5], k = 2
Output: 9
Explanation:
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 * 104edges.length == n - 1edges[i] = [ui, vi]0 <= ui, vi < nnums.length == n-5 * 104 <= nums[i] <= 5 * 1041 <= k <= 50The input is generated such that edges represents a valid tree.
3544. Subtree Inversion Sum
Hard
50 Points
Array
Dynamic Programming
Tree
Depth-First Search
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:
Return the maximum possible sum of the tree's node values after applying inversion operations.
Examples
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:
Example 2
Input: edges = [[0,1],[1,2],[2,3],[3,4]], nums = [-1,3,-2,4,-5], k = 2
Output: 9
Explanation:
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 * 104edges.length == n - 1edges[i] = [ui, vi]0 <= ui, vi < nnums.length == n-5 * 104 <= nums[i] <= 5 * 1041 <= k <= 50The input is generated such that edges represents a valid tree.