核心思路换根DP将节点权值统一转换 w[i] 2 * good[i] - 1 好节点贡献1坏节点贡献-1问题转化为对每个节点求包含该节点的连通子图最大权值和。采用经典二次扫描换根法1. 后序DFS计算 dp[u] ——以 u 为根的子树中包含 u 的连通子图最大权值和仅合并权值为正的子树。2. 前序DFS计算 up[u] ——从 u 的父节点方向延伸的最大贡献结合子树 dp 得到每个节点的最终答案。递归实现简洁版适合 n ≤ 1000gofunc maxSubgraphScore(n int, edges [][]int, good []int) []int {// 构建邻接表adj : make([][]int, n)for _, e : range edges {u, v : e[0], e[1]adj[u] append(adj[u], v)adj[v] append(adj[v], u)}// 转换节点权值w : make([]int, n)for i : range good {w[i] 2*good[i] - 1}dp : make([]int, n) // 子树内包含u的最大连通权值和up : make([]int, n) // 父方向延伸的最大贡献ans : make([]int, n)// 第一次后序遍历计算dp数组var dfs1 func(u, fa int)dfs1 func(u, fa int) {dp[u] w[u]for _, v : range adj[u] {if v fa {continue}dfs1(v, u)if dp[v] 0 {dp[u] dp[v]}}}// 第二次前序遍历换根计算up与答案var dfs2 func(u, fa int)dfs2 func(u, fa int) {ans[u] dp[u] max(0, up[u])for _, v : range adj[u] {if v fa {continue}// 父节点u去掉v子树后的正贡献总和otherPosSum : dp[u] - w[u] - max(0, dp[v])up[v] w[u] max(0, up[u]) max(0, otherPosSum)dfs2(v, u)}}dfs1(0, -1)dfs2(0, -1)return ans}func max(a, b int) int {if a b {return a}return b}迭代实现防栈溢出适配大规模数据Go 默认递归深度有限链式结构的大树会触发栈溢出迭代版更稳定gofunc maxSubgraphScore(n int, edges [][]int, good []int) []int {adj : make([][]int, n)for _, e : range edges {u, v : e[0], e[1]adj[u] append(adj[u], v)adj[v] append(adj[v], u)}w : make([]int, n)for i : range good {w[i] 2*good[i] - 1}dp : make([]int, n)up : make([]int, n)ans : make([]int, n)// 第一次迭代后序DFS计算dptype stackNode struct {u intfa intvisited bool}stack : []stackNode{{0, -1, false}}for len(stack) 0 {node : stack[len(stack)-1]stack stack[:len(stack)-1]u, fa : node.u, node.faif !node.visited {stack append(stack, stackNode{u, fa, true})// 逆序入栈保证遍历顺序一致不影响最终结果for i : len(adj[u]) - 1; i 0; i-- {v : adj[u][i]if v ! fa {stack append(stack, stackNode{v, u, false})}}} else {dp[u] w[u]for _, v : range adj[u] {if v fa {continue}if dp[v] 0 {dp[u] dp[v]}}}}// 第二次BFS前序计算up与答案queue : [][]int{{0, -1}}for len(queue) 0 {cur : queue[0]queue queue[1:]u, fa : cur[0], cur[1]ans[u] dp[u] max(0, up[u])for _, v : range adj[u] {if v fa {continue}otherPosSum : dp[u] - w[u] - max(0, dp[v])up[v] w[u] max(0, up[u]) max(0, otherPosSum)queue append(queue, []int{v, u})}}return ans}func max(a, b int) int {if a b {return a}return b}复杂度分析- 时间复杂度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。