题目准确题意给定一棵含 n 个节点的无向树 good[i] 1 表示节点 i 是好节点 0 表示坏节点。连通子图的得分 子图内好节点数量 - 坏节点数量。对每个节点 i 求包含节点 i 的所有连通子图的最大得分返回长度为 n 的结果数组。权重转换核心简化每个节点的贡献可统一为权值w[i] 2 \times good[i] - 1- 好节点贡献 1- 坏节点贡献 -1问题转化为对每个节点求包含该节点的连通子图最大权值和经典换根DP二次扫描法问题。算法思路换根DP第一次后序DFS子树DP- dp[u] 以 u 为根的子树中包含 u 的连通子图最大权值和- 转移仅合并权值为正的子树dp[u] w[u] \sum_{v \in 子节点} \max(0, dp[v])第二次前序DFS换根计算父方向贡献- up[u] 从 u 的父节点方向延伸、包含父节点的最大连通权值和不包含 u 本身- 转移父节点自身权值 父方向正贡献 父节点其他子树的正贡献之和\begin{align*}\text{其他子树正贡献和} dp[fa] - w[fa] - \max(0, dp[u]) \\up[u] w[fa] \max(0, up[fa]) \max(0, \text{其他子树正贡献和})\end{align*}最终答案每个节点的最大得分 子树方向最大值 父方向正贡献ans[u] dp[u] \max(0, up[u])Java 递归实现简洁版javaimport java.util.*;class Solution {ListInteger[] adj;int[] dp; // 子树内包含u的最大连通权值和int[] up; // 父方向延伸的最大贡献包含父节点int[] w; // 节点权值int[] ans;public int[] maxSubgraphScore(int n, int[][] edges, int[] good) {// 1. 建邻接表adj new ArrayList[n];for (int i 0; i n; i) adj[i] new ArrayList();for (int[] e : edges) {int u e[0], v e[1];adj[u].add(v);adj[v].add(u);}// 2. 初始化节点权值w new int[n];for (int i 0; i n; i) {w[i] 2 * good[i] - 1;}dp new int[n];up new int[n];ans new int[n];// 3. 第一次后序DFS计算子树dpdfs1(0, -1);// 4. 第二次前序DFS换根计算up与答案dfs2(0, -1);return ans;}// 后序计算子树dpvoid dfs1(int u, int fa) {dp[u] w[u];for (int v : adj[u]) {if (v fa) continue;dfs1(v, u);if (dp[v] 0) {dp[u] dp[v];}}}// 前序换根计算up同步计算答案void dfs2(int u, int fa) {ans[u] dp[u] Math.max(0, up[u]);for (int v : adj[u]) {if (v fa) continue;// 计算父节点u去掉v子树后的正贡献和int otherPosSum dp[u] - w[u] - Math.max(0, dp[v]);// up[v] u自身权值 u的父方向正贡献 u的其他子树正贡献up[v] w[u] Math.max(0, up[u]) Math.max(0, otherPosSum);dfs2(v, u);}}}Java 迭代实现防栈溢出适配1e5节点AC链式树递归会触发栈溢出迭代版更稳定javaimport java.util.*;class Solution {static class StackNode {int u, fa;boolean visited;StackNode(int u, int fa, boolean visited) {this.u u;this.fa fa;this.visited visited;}}public int[] maxSubgraphScore(int n, int[][] edges, int[] good) {ListInteger[] adj new ArrayList[n];for (int i 0; i n; i) adj[i] new ArrayList();for (int[] e : edges) {adj[e[0]].add(e[1]);adj[e[1]].add(e[0]);}int[] w new int[n];for (int i 0; i n; i) w[i] 2 * good[i] - 1;int[] dp new int[n];int[] up new int[n];int[] ans new int[n];// 第一次后序DFS计算dpDequeStackNode st new ArrayDeque();st.push(new StackNode(0, -1, false));while (!st.isEmpty()) {StackNode node st.pop();int u node.u, fa node.fa;if (!node.visited) {st.push(new StackNode(u, fa, true));for (int v : adj[u]) {if (v ! fa) st.push(new StackNode(v, u, false));}} else {dp[u] w[u];for (int v : adj[u]) {if (v fa) continue;if (dp[v] 0) dp[u] dp[v];}}}// 第二次前序BFS计算up与ansQueueint[] q new ArrayDeque();q.offer(new int[]{0, -1});while (!q.isEmpty()) {int[] cur q.poll();int u cur[0], fa cur[1];ans[u] dp[u] Math.max(0, up[u]);for (int v : adj[u]) {if (v fa) continue;int otherPosSum dp[u] - w[u] - Math.max(0, dp[v]);up[v] w[u] Math.max(0, up[u]) Math.max(0, otherPosSum);q.offer(new int[]{v, u});}}return ans;}}复杂度与验证复杂度- 时间O(n)每个节点仅遍历两次- 空间O(n)邻接表 DP数组样例验证输入 n3, edges[[0,1],[1,2]], good[1,0,1]- 权值 [1, -1, 1]- 输出 [1, 1, 1]- 解释包含任意节点的最优连通子图都是全选得分 2好-1坏 1输入 n2, edges[[0,1]], good[1,0]- 输出 [1, 0]- 解释节点0最优选自身得分1节点1最优选两个节点1好1坏得分0需要我补充更多边界用例的推导过程吗