题目重点：每个节点权重为 +1 或 -1，求包含它的连通子图最大权重；两遍树 DP 分别累计子树和父侧贡献。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入是一棵编号 1..n 的无向树；强节点权重 +1，弱节点权重 -1。
- 连通子图必须包含查询节点，允许只选该节点，所以结果可为 -1。
- n=0 非题目情形，训练实现返回空列表；非法 0/1 标签或非树边集拒绝。
解题路线
- 先固定根 1。定义 down[u]：只使用 u 子树内节点且必须包含 u 的最佳连通权重。每个儿子 v 若 down[v]>0 才有必要接入，故 down[u]=w[u]+Σmax(0,down[v])。
- 第二遍把父侧贡献传给儿子。若已知全树包含 u 的最优值 ans[u]，排除儿子 v 的贡献后，父侧候选为 ans[u]−max(0,down[v])；若它为正才从 v 连接过去。
- 因此 ans[v]=down[v]+max(0,ans[u]−max(0,down[v]))。从根向外遍历，一次求出所有节点。
- 代码用迭代 DFS/BFS 形成 parent/order，避免大树递归栈溢出；倒序算 down，正序算 ans。
手动走一遍
题目星图：根 1 为弱，子节点权重依次 -1,+1,-1。down[1]=−1+max(0,−1)+max(0,1)+max(0,−1)=0。对强节点 3，父侧=0−1=−1，不加入，ans[3]=1；弱叶 2 的父侧=0，ans[2]=−1，弱叶 4 同理，得到 [0,−1,1,−1]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def maximum_connected_strength(
strong: list[int], edges: list[tuple[int, int]]
) -> list[int]:
"""For every 1-based node, best connected subgraph containing it."""
n = len(strong)
if n == 0:
if edges:
raise ValueError("edges without nodes")
return []
if any(value not in (0, 1) for value in strong) or len(edges) != n - 1:
raise ValueError("expected a binary-labelled tree")
graph = [[] for _ in range(n)]
for u, v in edges:
if not 1 <= u <= n or not 1 <= v <= n or u == v:
raise ValueError("invalid edge")
u -= 1
v -= 1
graph[u].append(v)
graph[v].append(u)
parent = [-1] * n
parent[0] = 0
order = [0]
for u in order:
for v in graph[u]:
if parent[v] == -1:
parent[v] = u
order.append(v)
if len(order) != n:
raise ValueError("disconnected or cyclic input")
down = [1 if value else -1 for value in strong]
for u in reversed(order):
for v in graph[u]:
if parent[v] == u:
down[u] += max(0, down[v])
result = [0] * n
result[0] = down[0]
for u in order:
for v in graph[u]:
if parent[v] == u:
outside = result[u] - max(0, down[v])
result[v] = down[v] + max(0, outside)
return result
if __name__ == "__main__":
assert maximum_connected_strength([0, 0, 1, 0], [(1, 2), (1, 3), (1, 4)]) == [0, -1, 1, -1]
复杂度
两遍每条树边各处理常数次，O(n) 时间；邻接表、parent/order、down/ans 均 O(n) 空间。
易错点与追问
容易失分的边界
- 把空连通子图作为合法答案，错误地把孤立弱节点结果改成 0。
- 把强弱标签 0/1 直接相加，没有将弱节点映射为 -1。
- 只做一次子树 DP，漏掉从父侧连接过来的正贡献。
- 第二遍未减去该儿子对父节点最优值的贡献，造成重复计数。
- 大树递归 DFS 超出运行时栈深。
继续深挖
- 如果节点是任意整数权重，公式是否仍成立？
- 若图有环，为什么树 DP 不再直接适用？
- 如何恢复每个节点对应的一组最优连通子图节点，而不显式输出 O(n²) 数据？
