Tap here to switch tabs
Problem
Submissions

Problem: Subtree Inversion Sum

Subtree Inversion Sum gives a rooted tree and node values. Select nodes to negate their subtrees, keeping selected ancestors at least k edges apart, and maximize the total.

Statement

You are given an undirected tree with nn nodes numbered from 00 to n−1n - 1, rooted at node 00. The tree is represented by a 2D2 {D} integer array edges of length n−1n - 1, where edges[i] =[ui,vi]= [u_i, v_i] denotes an edge between nodes uiu_i and viv_i.

You are also given an integer array nums of length nn, where nums[i] represents the value assigned to node ii, and a positive integer k.

You can select a subset of nodes and perform an inversion operation on each selected node. When an inversion operation is performed on a node uu, the value of every node in the subtree rooted at uu is multiplied by −1-1.

A selection of nodes is valid if, for any two selected nodes uu and vv where vv lies in the subtree rooted at uu, the distance between uu and vv is at least kk.

Return the maximum possible sum of all values in nums after applying any valid set of inversion operations.

Constraints:

  • 2≤n≤5×1042 \leq n \leq 5 \times 10^4

  • edges.length =n−1= n - 1

  • edges[i] =[ui,vi]= [u_i, v_i]

  • 0≤ui,vi<n0 \leq u_i, v_i < n

  • nums.length =n= n

  • −5×104≤-5 \times 10^4 \leq nums[i] ≤5×104\leq 5 \times 10^4

  • 1≤k≤501 \leq k \leq 50

  • The input is generated such that edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Subtree Inversion Sum

Subtree Inversion Sum gives a rooted tree and node values. Select nodes to negate their subtrees, keeping selected ancestors at least k edges apart, and maximize the total.

Statement

You are given an undirected tree with nn nodes numbered from 00 to n−1n - 1, rooted at node 00. The tree is represented by a 2D2 {D} integer array edges of length n−1n - 1, where edges[i] =[ui,vi]= [u_i, v_i] denotes an edge between nodes uiu_i and viv_i.

You are also given an integer array nums of length nn, where nums[i] represents the value assigned to node ii, and a positive integer k.

You can select a subset of nodes and perform an inversion operation on each selected node. When an inversion operation is performed on a node uu, the value of every node in the subtree rooted at uu is multiplied by −1-1.

A selection of nodes is valid if, for any two selected nodes uu and vv where vv lies in the subtree rooted at uu, the distance between uu and vv is at least kk.

Return the maximum possible sum of all values in nums after applying any valid set of inversion operations.

Constraints:

  • 2≤n≤5×1042 \leq n \leq 5 \times 10^4

  • edges.length =n−1= n - 1

  • edges[i] =[ui,vi]= [u_i, v_i]

  • 0≤ui,vi<n0 \leq u_i, v_i < n

  • nums.length =n= n

  • −5×104≤-5 \times 10^4 \leq nums[i] ≤5×104\leq 5 \times 10^4

  • 1≤k≤501 \leq k \leq 50

  • The input is generated such that edges represents a valid tree.