Leetcode 3544. Subtree Inversion Sum

• Leetcode 3544. Subtree Inversion Sum
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3544. Subtree Inversion Sum

1. 解题思路

这一题我的思路上就是一个动态规划的思路，因为原则上我们只需要遍历一下所有的状态即可，但是这样显然时间复杂度过高，因此我们采用一个动态规划的思路用空间换时间，即可完成上述题目的解答。

具体到实现上也是比较简单，首先就是利用边的内容获取一下整的这个树的结构。

然后我们就是一个遍历，遍历的时候需要记录一下每一个节点当前的正负相位，是否可以相位反转以及如果不可以反转的话，还需要多少深度才能够进行相位反转。

2. 代码实现

给出python代码实现如下：

class Solution:def subtreeInversionSum(self, edges: List[List[int]], nums: List[int], k: int) -> int:def get_graph(edges):graph = defaultdict(list)for u, v in edges:graph[u].append(v)graph[v].append(u)new_graph = defaultdict(list)def _dfs(u, p):for v in graph[u]:if v == p:continuenew_graph[u].append(v)_dfs(v, u)return _dfs(0, -1)return new_graphgraph = get_graph(edges)@lru_cache(None)def dfs(u, flag, d):if d == 0 or d >= k:ans = flag * nums[u]for v in graph[u]:ans += dfs(v, flag, 0)rev = - (flag * nums[u])for v in graph[u]:rev += dfs(v, -flag, 1)return max(ans, rev)else:ans = flag * nums[u]for v in graph[u]:ans += dfs(v, flag, d+1)return ansreturn dfs(0, 1, 0)

提交代码评测得到：耗时6642ms，占用内存774.9MB。