树的递归与返回值设计

import sys

sys.setrecursionlimit(300000)                     # 链状树的递归深度可能接近 N
data = sys.stdin.read().split()
n = int(data[0])
val = [0] + [int(x) for x in data[1:1 + n]]      # 编号 1..N
children = [[] for _ in range(n + 1)]
is_child = [False] * (n + 1)
for i in range(n - 1):
    p, c = int(data[1 + n + 2 * i]), int(data[2 + n + 2 * i])   # p 是 c 的父节点
    children[p].append(c)
    is_child[c] = True
root = next(u for u in range(1, n + 1) if not is_child[u])     # 唯一不是任何人孩子的节点
best = 0


def dfs(u):
    global best
    family = val[u]                               # 小家庭 = 自己 + 直接孩子（孙辈不算）
    for c in children[u]:
        family += val[c]
        dfs(c)                                    # 继续往下：每个节点各自算一次自己的小家庭
    if family > best:
        best = family


dfs(root)
print(best)

用第 04 节的五节点 → 23 和根是 2 号的 3 / 5 6 7 / 2 1 / 2 3 → 18 核对；链状树靠开头的递归上限设置才能跑完。思路与题目页参考题解（Java / C / Go）相同。

import sys

sys.setrecursionlimit(300000)
nums = [int(x) for x in sys.stdin.read().split()]   # 数组式二叉树：下标 i 的孩子是 2i+1、2i+2，-1 是空节点
n = len(nums)
best = 0


def dfs(i, acc):                                  # acc = 根到 i 的父节点为止的累计耗时（参数向下传）
    global best
    total = acc + nums[i]                         # 传到 i 本人的时刻（根的值是 0）
    l, r = 2 * i + 1, 2 * i + 2
    has_l = l < n and nums[l] != -1
    has_r = r < n and nums[r] != -1
    if not has_l and not has_r:                   # 叶子：一条根到叶的路走完，更新最晚时刻
        if total > best:
            best = total
        return
    if has_l:
        dfs(l, total)
    if has_r:
        dfs(r, total)


dfs(0, 0)
print(best)

用题面示例 → 38 和 0 2 3 4 → 6 核对。

import sys

sys.setrecursionlimit(300000)
lines = sys.stdin.read().split("\n")
inorder = [int(x) for x in lines[0].split()]
preorder = [int(x) for x in lines[1].split()]
pos = {v: i for i, v in enumerate(inorder)}       # 值 → 在中序里的位置（题目保证值互不相同）
out = []                                          # 新树的中序遍历


def build(pre_l, in_l, in_r):                     # 返回：这段子树在原树里的节点值之和；顺便按中序把新值写进 out
    if in_l > in_r:
        return 0
    root_val = preorder[pre_l]
    k = pos[root_val]                             # 根在中序里的位置：左边是左子树，右边是右子树
    left_size = k - in_l
    left_sum = build(pre_l + 1, in_l, k - 1)      # 左子树：前序紧跟根，中序在根左边
    out.append(left_sum + 0)                      # 先占位，下面补上右子树和
    idx = len(out) - 1
    right_sum = build(pre_l + 1 + left_size, k + 1, in_r)
    out[idx] = left_sum + right_sum               # 新值 = 左子树和 + 右子树和（中序位置：左子树之后、右子树之前）
    return left_sum + right_sum + root_val        # 向上返回整棵子树在原树里的和


build(0, 0, len(inorder) - 1)
print(" ".join(map(str, out)))

用题面示例（中序 8 12 -3 6 -10 9 -7、前序 -3 12 8 6 9 -10 -7 → 0 8 18 -8 0 -17 0）核对。还原与求和在同一次递归里完成。

def richest_family(n, val, edges):
    # val[1..n]：财富；edges：(父, 子)；小家庭 = 自己 + 直接孩子
    children = [[] for _ in range(n + 1)]
    is_child = [False] * (n + 1)
    for p, c in edges:
        children[p].append(c)
        is_child[c] = True
    root = next(u for u in range(1, n + 1) if not is_child[u])
    best = 0
    stack = [root]                              # 用显式栈遍历：每个节点各自算一次自己的小家庭
    while stack:
        u = stack.pop()
        family = val[u] + sum(val[c] for c in children[u])
        best = max(best, family)
        stack.extend(children[u])
    return best

V = [0, 10, 5, 8, 1, 2]
assert richest_family(5, V, [(1, 2), (1, 3), (2, 4), (2, 5)]) == 23    # 第 04 节：1 + 直接孩子 2、3
assert richest_family(3, [0, 5, 6, 7], [(2, 1), (2, 3)]) == 18       # 根不是 1 号：2 + 孩子 1、3
assert richest_family(3, [0, 1, 1, 100], [(1, 2), (2, 3)]) == 101    # 最富的小家庭在中间
assert richest_family(1, [0, 7], []) == 7                            # 单节点

用显式栈遍历，不受递归深度限制；每个节点当场算自己的小家庭。

def whisper_time(nums):
    # 数组式二叉树：下标 i 的孩子是 2i+1、2i+2，-1 是空节点；节点值 = 父传子的耗时
    n = len(nums)
    best = 0
    def dfs(i, acc):                            # acc：根到 i 的父节点为止的累计（参数向下传）
        nonlocal best
        total = acc + nums[i]
        l, r = 2 * i + 1, 2 * i + 2
        has_l = l < n and nums[l] != -1
        has_r = r < n and nums[r] != -1
        if not has_l and not has_r:             # 叶子处更新
            best = max(best, total)
            return
        if has_l:
            dfs(l, total)
        if has_r:
            dfs(r, total)
    dfs(0, 0)
    return best

assert whisper_time([0, 9, 20, -1, -1, 15, 7, -1, -1, -1, -1, 3, 2]) == 38   # P3904 题面示例（第 05 节表）
assert whisper_time([0, 2, 3, 4]) == 6                                       # 第 05 节小例
assert whisper_time([0]) == 0                                                # 只有根
assert whisper_time([0, 5, -1, 4]) == 9                                      # 右空、左链

最后一条：右孩子是空节点、左孩子 5 的左孩子是 4 → 0 + 5 + 4 = 9。