核心思路换根DP每个节点贡献统一转换为权值 w[i] 2 * good[i] - 1 好节点1坏节点-1。问题转化为对每个节点求包含该节点的连通子图最大权值和使用经典换根DP二次扫描法1. 后序DFS计算 dp[u] ——以u为根的子树中包含u的连通子图最大权值和仅合并权值为正的子树。2. 前序DFS计算 up[u] ——从u的父节点方向延伸的最大贡献再结合子树结果得到每个节点的最终答案。递归实现简洁易读适合n≤1000pythonfrom typing import Listclass Solution:def maxSubgraphScore(self, n: int, edges: List[List[int]], good: List[int]) - List[int]:# 构建邻接表adj [[] for _ in range(n)]for u, v in edges:adj[u].append(v)adj[v].append(u)w [2 * x - 1 for x in good] # 节点权值转换dp [0] * n # 子树内包含u的最大连通权值和up [0] * n # 父方向延伸的最大贡献ans [0] * n# 第一次后序遍历计算子树dpdef dfs1(u: int, fa: int) - None:dp[u] w[u]for v in adj[u]:if v fa:continuedfs1(v, u)if dp[v] 0:dp[u] dp[v]# 第二次前序遍历换根计算up与答案def dfs2(u: int, fa: int) - None:ans[u] dp[u] max(0, up[u])for v in adj[u]:if v fa:continue# 父节点u去掉v子树后的正贡献总和other_pos_sum dp[u] - w[u] - max(0, dp[v])up[v] w[u] max(0, up[u]) max(0, other_pos_sum)dfs2(v, u)dfs1(0, -1)dfs2(0, -1)return ans迭代实现防栈溢出适配大数据Python默认递归深度约1000链式大树会触发栈溢出推荐使用迭代版pythonfrom typing import Listfrom collections import dequeclass Solution:def maxSubgraphScore(self, n: int, edges: List[List[int]], good: List[int]) - List[int]:adj [[] for _ in range(n)]for u, v in edges:adj[u].append(v)adj[v].append(u)w [2 * x - 1 for x in good]dp [0] * nup [0] * nans [0] * n# 第一次迭代后序DFS计算dp数组stack [(0, -1, False)]while stack:u, fa, visited stack.pop()if not visited:stack.append((u, fa, True))for v in adj[u]:if v ! fa:stack.append((v, u, False))else:dp[u] w[u]for v in adj[u]:if v fa:continueif dp[v] 0:dp[u] dp[v]# 第二次BFS前序计算up与答案q deque([(0, -1)])while q:u, fa q.popleft()ans[u] dp[u] max(0, up[u])for v in adj[u]:if v fa:continueother_pos_sum dp[u] - w[u] - max(0, dp[v])up[v] w[u] max(0, up[u]) max(0, other_pos_sum)q.append((v, u))return ans复杂度与验证- 时间复杂度O(n)每个节点仅遍历两次- 空间复杂度O(n)邻接表与DP数组样例验证输入 n3, edges[[0,1],[1,2]], good[1,0,1]输出 [1, 1, 1]解释任意节点的最优连通子图都是全选得分2个好节点-1个坏节点1。输入 n2, edges[[0,1]], good[1,0]输出 [1, 0]解释节点0最优只选自身得分1节点1最优全选1好1坏得分0。
