Subtree Inversion Sum
You are given an undirected tree rooted at node 0, with n nodes numbered from 0 to n - 1.
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.
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
Example 2
Input: edges = [[0,1],[1,2],[2,3],[3,4]], nums = [-1,3,-2,4,-5], k = 2
Output: 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 * 10^4
- edges.length == n - 1
- edges[i] = [ui, vi]
- 0 <= ui, vi < n
- nums.length == n
- -5 * 10^4 <= nums[i] <= 5 * 10^4
- 1 <= k <= 50
- The input is generated such that edges represents a valid tree.
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.