如何用四种方法计算D005子树大小？

1674 Subordinates CSES Python推荐使用 Pypy3 编译器和一次性读入字符串的方式和方法一或方法四，不然会被卡掉最后一个点 最基础的树论题，考察对递归的应用和对树形结构的理解。 返回值累加 DFS 函数返回当前子树的大小，父节点拿到子节点的返回值后累加到自己身上。 sz = [0] * (n + 1) def dfs(u, fa=-1): cur = 1 for v in g[u]: if v != fa: cur += dfs(v, u) sz[u] = cur return cur dfs(1) # 1-based 在求数的重心时常用这种方法。 全局更新 此时 DFS 函数不返回子树大小而是在回溯时利用引用或全局数组来更新子树大小。这种写法 DFS 的返回值求别的东西，子树大小只是副产物。 sz = [0] * (n + 1) def dfs(u, fa=-1): sz[u] = 1 for v in g[u]: if v != fa: dfs(v, u) sz[u] += sz[v] dfs(1) 时间戳差值 利用时间戳的性质可知，子树的大小为：离开时间 - 进入时间 + 1 。 timer = 0 tin = [0] * (n + 1) tout = [0] * (n + 1) sz = [0] * (n + 1) def dfs(u, fa=-1): nonlocal timer timer += 1 tin[u] = timer for v in g[u]: if v != fa: dfs(v, u) tout[u] = timer sz[u] = tout[u] - tin[u] + 1 dfs(1) 栈模拟递归 递归开销太大了，很容易超时和栈溢出（ \(2\times 10^5\) 时），所以会手写递归是非常重要的。方法二三会超时，但一和四不会。 拓扑逆序法 逻辑和 bfs 很相似。 order = [] # 存先序结果，即 dfs 序 sz = [1] * (n + 1) fa = [-1] * (n + 1) st = [1] while st: u = st.pop() order.append(u) for v in g[u]: if v != fa[u]: fa[v]= u st.append(v) for i in range(len(order)-1, -1, -1): u = order[i] p = fa[u] if p != -1: sz[p] += sz[u] 状态标记法 使用 (节点，状态) 二元组 当状态为 \(0\) 时，表示第一次访问的节点。对应递归函数的入口用于处理先序的逻辑。 状态为 \(1\) 时，表示子节点已经全部访问过，回溯时该部分用于处理后序的逻辑。 fa = [-1] * (n + 1) sz = [0] * (n + 1) st = [(1, 0)] while st: u, state = st.pop() if state == 0: # 先序逻辑，比如 tin[u] = len(order) 等操作 st.append((u, 1)) for v in g[u]: # 注意这里按一些题目要求可能需要排序 if v != fa[u]: fa[v] = u st.append((v, 0)) else: # 后序遍历的逻辑 cur = 1 for v in g[u]: if v != fa[u]: cur += sz[v] sz[u] = cur