题目重点：电面公开把每个节点改成原树子树和，追问大量子树但线程有限；先用后序遍历证明正确，再分析依赖与工作池。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版输入一棵有根树：values[node] 是原始整数值，children[node] 给有序子节点；输出同样节点集合的 node→subtreeSum，新映射不修改 values。
- 所有节点都可从 root 到达，节点只有一个父亲；环、共享子节点或未知子节点报错。题目未公开树形数据结构和并行 API。
- 并行追问只讨论正确调度与规模取舍，不宣称有限线程一定比顺序更快。
解题路线
- 后序计算 S(node)=originalValue(node)+ΣS(child)；必须先拿到每个子节点的结果，再写父节点，且读的始终是原始值，避免原地修改的混淆。
- 示例用显式 enter/exit 栈做后序，处理完成节点时读取 child 结果；校验输入是单根树并输出新 map。
- 并行时把就绪叶节点放入有界工作队列，每个父节点维护未完成子节点计数；最后一个 child 完成时把父节点变为可执行。工作线程数量为 P，避免每节点新建线程。
- 若每个节点工作只是一次加法，线程调度开销通常超过收益；只对大子树或复杂节点计算做任务切分，需保证同一父节点聚合的原子性。
- 随机树与独立递归后序参考做 10,000 组对照，包括负值、深链和多分支。
手动走一遍
根 A 值 2，孩子 B 值 3、C 值 -1，B 有孩子 D 值 4。新树对应 D=4、B=7、C=-1、A=8。并行时 B 与 C 可并行计算，但 A 必须等 B/C 都完成；若 P=2，可让一个线程处理 B 子树，另一个处理 C。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Rewrite each node's value as its original subtree sum, without mutation."""
def subtree_sums(root: str, values: dict[str, int], children: dict[str, list[str]]) -> dict[str, int]:
if root not in values:
raise ValueError("missing root")
if any(child not in values for group in children.values() for child in group):
raise ValueError("unknown child")
result = {}
visiting = set()
visited = set()
stack = [(root, False)]
while stack:
node, exiting = stack.pop()
if exiting:
result[node] = values[node] + sum(result[child] for child in children.get(node, []))
visiting.remove(node)
visited.add(node)
continue
if node in visiting or node in visited:
raise ValueError("not a tree")
visiting.add(node)
stack.append((node, True))
stack.extend((child, False) for child in reversed(children.get(node, [])))
if visited != set(values):
raise ValueError("disconnected nodes")
return result
复杂度
N 个节点、E=N−1 边，顺序后序 O(N+E) 时间和 O(N+E) 输出/工作空间。并行的理想下界是 max(总工作/P,最长根叶依赖链)，还要加队列与同步开销；单链树无法靠兄弟并行加速。
易错点与追问
容易失分的边界
- 父节点在所有 child 结果完成前求和，得到部分结果。
- 原地覆盖节点值后又把它当原始值重复累加。
- 对每个子树开新线程，在‘无数多个子树’时耗尽线程和内存。
- worker 阻塞等待自己提交的 child future，固定大小线程池可能死锁。
- 宣称树后序一定能线性加速，忽略关键路径和调度成本。
继续深挖
- 每个节点还有昂贵 I/O 时，工作池和背压怎样调？
- 若树数据跨机器分片，如何处理父子归属与重试幂等？
- 若需要增量更新一个叶值，哪些祖先和受影响？
