3544. Subtree Inversion Sum Hard

1/**
2 * [3544] Subtree Inversion Sum
3 *
4 * <p data-end="551" data-start="302">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.
5 * <p data-end="670" data-start="553">You are also given an integer array nums of length n, where nums[i] represents the value at node i, and an integer k.
6 * <p data-end="763" data-start="672">You may perform inversion operations on a subset of nodes subject to the following rules:
7 * <ul data-end="1247" data-start="765">
8 * 	<li data-end="890" data-start="765">
9 * 	<p data-end="799" data-start="767"><strong data-end="799" data-start="767">Subtree Inversion Operation:
10 * 	<ul data-end="890" data-start="802">
11 * 		<li data-end="887" data-start="802">
12 * 		<p data-end="887" data-start="804">When you invert a node, every value in the <span data-keyword="subtree-of-node">subtree</span> rooted at that node is multiplied by -1.
13 * 		
14 * 	
15 * 	
16 * 	<li data-end="1247" data-start="891">
17 * 	<p data-end="931" data-start="893"><strong data-end="931" data-start="893">Distance Constraint on Inversions:
18 * 	<ul data-end="1247" data-start="934">
19 * 		<li data-end="1020" data-start="934">
20 * 		<p data-end="1020" data-start="936">You may only invert a node if it is "sufficiently far" from any other inverted node.
21 * 		
22 * 		<li data-end="1247" data-start="1023">
23 * 		<p data-end="1247" data-start="1025">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.
24 * 		
25 * 	
26 * 	
27 * 
28 * <p data-end="1358" data-start="1249">Return the maximum possible sum of the tree's node values after applying inversion operations.
29 *  
30 * <strong class="example">Example 1:
31 * <div class="example-block">
32 * Input: <span class="example-io">edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], nums = [4,-8,-6,3,7,-2,5], k = 2</span>
33 * Output: <span class="example-io">27</span>
34 * Explanation:
35 * <img alt="" src="https://assets.leetcode.com/uploads/2025/03/29/tree1-3.jpg" style="width: 311px; height: 202px;" />
36 * 
37 * 	Apply inversion operations at nodes 0, 3, 4 and 6.
38 * 	The final <code data-end="1726" data-start="1720">nums array is <code data-end="1760" data-start="1736">[-4, 8, 6, 3, 7, 2, 5], and the total sum is 27.
39 * </div>
40 * <strong class="example">Example 2:
41 * <div class="example-block">
42 * Input: <span class="example-io">edges = [[0,1],[1,2],[2,3],[3,4]], nums = [-1,3,-2,4,-5], k = 2</span>
43 * Output: <span class="example-io">9</span>
44 * Explanation:
45 * <img alt="" src="https://assets.leetcode.com/uploads/2025/03/29/tree2-1.jpg" style="width: 371px; height: 71px;" />
46 * 
47 * 	Apply the inversion operation at node 4.
48 * 	<li data-end="2632" data-start="2483">The final <code data-end="2569" data-start="2563">nums array becomes <code data-end="2603" data-start="2584">[-1, 3, -2, 4, 5], and the total sum is 9.
49 * </div>
50 * <strong class="example">Example 3:
51 * <div class="example-block">
52 * Input: <span class="example-io">edges = [[0,1],[0,2]], nums = [0,-1,-2], k = 3</span>
53 * Output: <span class="example-io">3</span>
54 * Explanation:
55 * Apply inversion operations at nodes 1 and 2.
56 * </div>
57 *  
58 * Constraints:
59 * 
60 * 	2 <= n <= 5 * 10^4
61 * 	edges.length == n - 1
62 * 	edges[i] = [ui, vi]
63 * 	0 <= ui, vi < n
64 * 	nums.length == n
65 * 	-5 * 10^4 <= nums[i] <= 5 * 10^4
66 * 	1 <= k <= 50
67 * 	The input is generated such that edges represents a valid tree.
68 * 
69 */
70pub struct Solution {}
71
72// problem: https://leetcode.com/problems/subtree-inversion-sum/
73// discuss: https://leetcode.com/problems/subtree-inversion-sum/discuss/?currentPage=1&orderBy=most_votes&query=
74
75// submission codes start here
76
77impl Solution {
78    pub fn subtree_inversion_sum(edges: Vec<Vec<i32>>, nums: Vec<i32>, k: i32) -> i64 {
79        
80    }
81}
82
83// submission codes end
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88
89    #[test]
90    fn test_3544() {
91    }
92}
93