这是 LeetCode 3544. 子树反转和 的 Java 实现。思路本题是树形 DP 记忆化搜索。核心观察 反转一个节点会影响其整个子树。约束条件要求若两个反转节点存在祖先关系则它们之间的距离边数必须至少为 k。状态定义 dp(u, steps, inverted) 表示- 以节点 u 为根的子树- steps距离最近一个祖先反转节点已经经过了多少条边上限为 k- inverted当前节点是否被反转即当前子树整体是否被乘了 -1转移- 若 steps k当前节点可以再次反转取 max(不反转, 反转)- 若 steps k当前节点不能反转只能继承当前状态- 对于子节点 v- 不反转 u子节点继承 min(steps 1, k)反转状态不变- 反转 u若允许子节点的 steps 重置为 1子节点距离新的反转点 1 步反转状态翻转初始状态 根节点 0 的 steps k表示根节点可以立即反转。复杂度 O(n · k) 状态数每个状态遍历所有子节点总复杂度 O(n · k)。---javaimport java.util.ArrayList;import java.util.Arrays;import java.util.List;class Solution {public long subtreeInversionSum(int[][] edges, int[] nums, int k) {final int n edges.length 1;int[] parent new int[n];Arrays.fill(parent, -1);SuppressWarnings(unchecked)ListInteger[] graph new List[n];Arrays.setAll(graph, i - new ArrayList());for (int[] edge : edges) {int u edge[0], v edge[1];graph[u].add(v);graph[v].add(u);}// memo[u][steps][inverted]: steps in [0, k], inverted in {0, 1}Long[][][] memo new Long[n][k 1][2];return dfs(graph, 0, k, false, nums, k, parent, memo);}private long dfs(ListInteger[] graph, int u, int stepsSinceInversion,boolean inverted, int[] nums, int k, int[] parent, Long[][][] memo) {if (memo[u][stepsSinceInversion][inverted ? 1 : 0] ! null) {return memo[u][stepsSinceInversion][inverted ? 1 : 0];}// 当前节点在反转/不反转状态下的值long num inverted ? -nums[u] : nums[u];// 如果当前节点再反转一次符号翻转long negNum -num;for (int v : graph[u]) {if (v parent[u]) continue;parent[v] u;// 不反转当前节点子节点继承 steps1上限 k反转状态不变num dfs(graph, v, Math.min(k, stepsSinceInversion 1),inverted, nums, k, parent, memo);// 如果距离足够远steps k可以尝试反转当前节点if (stepsSinceInversion k) {negNum dfs(graph, v, 1, !inverted, nums, k, parent, memo);}}// 如果当前可以反转取最大值否则只能不反转long res (stepsSinceInversion k) ? Math.max(num, negNum) : num;memo[u][stepsSinceInversion][inverted ? 1 : 0] res;return res;}}---验证- 示例 1edges[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], nums[4,-8,-6,3,7,-2,5], k2 → 27 ✓- 示例 2edges[[0,1],[1,2],[2,3],[3,4]], nums[-1,3,-2,4,-5], k2 → 9 ✓- 示例 3edges[[0,1],[0,2]], nums[0,-1,-2], k3 → 3 ✓