第 94 章 树上算法¶
配套例题：BISHI96 先序遍历、中序遍历和后序遍历、BISHI124 【模板】最近公共祖先（LCA） 来源：S3 day8 树上算法（DFS 序 / LCA / 倍增 / 树链剖分）；S2
tree.cpp二叉树基本结构；S4模板.docx「树」 前置：90-图的表示与遍历、45-倍增、61-BFS广度优先搜索、39-树状数组与线段树
树是「最简单的图」，也是竞赛里出现频率最高的结构。 它比一般图多出来的性质只有两条——无环和任意两点唯一路径—— 但就这两条撑起了一整套算法。
这一章的组织逻辑是：
树的性质与存储
↓
遍历（三种序） ← 一切树上算法的执行顺序
↓
┌─────────────┬──────────────┬─────────────┐
DFS 序 → 子树区间 直径 / 重心 LCA → 路径长度
（配数据结构） （全局特征） （两点关系）
↓ ↓
树链剖分（113 章） 树上差分（42 章）
贯穿全章的一条 Python 主线：树的高度可以达到 \(n\)（一条链）， 所以任何递归写法在 \(n \ge 10^4\) 时都会爆栈。 本章的每一个模板都是非递归的，而且尽可能把循环下沉到 C 层。
94.1 树的性质与判定¶
树：\(n\) 个点、无环、连通的无向图。
「三选二」定理¶
对一个有 \(n\) 个点、\(m\) 条边的无向图，下面三条里任意两条成立就能推出第三条， 此时图是树：
所以判定一个图是不是树，最省事的写法是：数边数 + 判连通。
# [片段] 判树：最省事的两条件写法
# m == n - 1 且连通 <=> 是树
ok = (m == n - 1) and count_components(n, start, adj) == 1
⚠️ 只判 \(m = n-1\) 是不够的：一个三角形加一个孤立点也是 4 点 3 边， 但它既不连通也有环。必须配上连通性判定（BFS 或并查集）。
基本性质表¶
| 性质 | 说明 |
|---|---|
| 任意两点间有唯一简单路径 | 这是树上一切「路径问题」的基础 |
| 加任意一条非树边 | 恰好产生一个环（次小生成树就靠这条，见 92.6） |
| 删任意一条树边 | 恰好分成两个连通块 |
| 度数和 | \(\sum \deg(v) = 2(n-1)\)，所以平均度数 \(< 2\) |
| 叶子 | \(\deg(v) = 1\) 的点；\(n \ge 2\) 的树至少有 2 个叶子 |
| 树一定是二分图 | 无环 ⟹ 无奇环（93.5） |
| 树的直径端点 | 一定是叶子 |
| \(n\) 个带标号点的不同树的个数 | \(n^{n-2}\)（Cayley 公式），配 Prüfer 序列 |
有根树与无根树¶
题目给的边通常是无向的（「\(x\) 与 \(y\) 相连」），
而绝大多数算法需要有根树（父亲、儿子、深度、子树）。
「定根」这个动作只是选一个点当根，然后一次遍历确定所有 parent：
| 概念 | 定义 |
|---|---|
par[u] |
\(u\) 的父亲；根的父亲设为 0（哨兵，省掉边界判断） |
dep[u] |
根到 \(u\) 的边数（或点数，看题目约定） |
sz[u] |
子树 \(u\) 的点数 |
| 换根 | 把根从 \(u\) 换到相邻的 \(v\)：\(sz'[v] = n\)，\(sz'[u] = n - sz[v]\)。这是「换根 DP」的核心 |
怎么找根： - 题目直接给（BISHI124 的 \(R\)）； - 有向父子边给出 ⟹ 入度为 0 的点（BISHI96）； - 无根树且答案与根无关 ⟹ 随便取 1 号点。
94.2 树的存储¶
| 方式 | 结构 | 适用 |
|---|---|---|
父数组 par[] |
一个长 \(n+1\) 的 list |
只需向上跳（并查集式、LCA 倍增） |
儿子表 kids[u] |
[[] for _ in range(n+1)] |
\(n \le 10^5\) 的有根树，最好写 |
CSR（start + adj） |
两个扁平数组 | \(n \ge 2\times10^5\) 必用（90.2） |
二叉树 left[] / right[] |
两个长 \(n+1\) 的 list |
二叉树专用（BISHI96），左右有序 |
| BFS 序 + 父数组 | order[] + par[] |
树上 DP 的最优表示（94.4） |
二叉树千万不要写成节点类：
# [片段] ❌ 竞赛里不要这么写
class Node: # n = 1e5 时是 1e5 个对象，慢且费内存
def __init__(self, val):
self.val, self.left, self.right = val, None, None
竞赛里点就是编号 \(1..n\)，用 left = [0] * (n+1)、right = [0] * (n+1) 两个数组，
0 表示空。下标访问比属性访问快一倍，内存少一个数量级。
94.3 二叉树的三种遍历（迭代实现）¶
| 遍历 | 顺序 | 特征 |
|---|---|---|
| 先序（preorder） | 根 → 左 → 右 | 第一个元素是根 |
| 中序（inorder） | 左 → 根 → 右 | BST 的中序是有序的 |
| 后序（postorder） | 左 → 右 → 根 | 最后一个元素是根；「先处理儿子」的场合 |
为什么必须写迭代版¶
一棵二叉树可以退化成一条长度 \(n\) 的链（\(1\to2\to3\to\cdots\to n\)）， 此时递归深度就是 \(n\)：
| 问题 | 后果 |
|---|---|
| CPython 默认递归上限 1000 | \(n \ge 1000\) 的链必 RecursionError |
sys.setrecursionlimit(200000) |
只改计数器，C 栈仍会溢出 → 段错误，没有任何报错 |
| 每层递归约 0.5 μs | 比迭代慢 2–3 倍 |
判据：二叉树遍历的递归深度上界就是 \(n\)。 BISHI96 的 \(n \le 10^5\) 已经远超上限，所以三种遍历全部必须迭代。 （另一条路是
threading.stack_size(1<<26)+ 开大栈线程，但要多起一个线程、 代码更绕，本教程一律用显式栈。）
模板一：先序 —— 栈里先压右后压左¶
def preorder_iter(root, left, right):
"""先序遍历（根 左 右）的迭代版。O(n)。
栈是后进先出，所以要「先压右孩子再压左孩子」，弹出时才是左先右后。
"""
out = []
st = [root] # 显式栈代替递归，深度不再受 CPython 限制
while st:
u = st.pop()
out.append(u) # 出栈即访问
r = right[u]
if r: # 0 表示空孩子，不入栈
st.append(r) # ★ 先压右
l = left[u]
if l:
st.append(l) # ★ 后压左（先弹出）
return out
模板二：中序 —— 一路向左压栈¶
def inorder_iter(root, left, right):
"""中序遍历（左 根 右）的迭代版。O(n)。
三步循环：一路向左把节点全压进栈 -> 弹出并访问 -> 转向它的右子树。
"""
out = []
st = [] # 栈里存「已进入、但左子树还没处理完」的点
u = root # u = 下一棵待展开的子树的根，0 表示空
while st or u: # 栈空且无待展开子树时才算结束
while u: # ① 一路向左
st.append(u)
u = left[u] # 走到最左端，那里是中序的第一个点
u = st.pop() # ② 弹出即访问（它的左子树已处理完）
out.append(u)
u = right[u] # ③ 转向右子树；为 0 则下轮直接再弹栈
return out
模板三：后序 —— 「根右左」再整体反转¶
def postorder_iter(root, left, right):
"""后序遍历（左 右 根）的迭代版。O(n)。
技巧：先按「根 右 左」跑一遍先序（把先序模板的左右压栈顺序对换），
得到的序列整体 reverse 就是「左 右 根」。
比「双栈法」和「标记访问次数法」都更短、更快。
"""
out = []
st = [root]
while st:
u = st.pop()
out.append(u) # 此刻 out 正在按「根 右 左」增长
l = left[u]
if l:
st.append(l) # ★ 与先序相反：先压左
r = right[u]
if r:
st.append(r) # 后压右（先弹出）
out.reverse() # ★ 一次 C 层反转
return out # 「根右左」的逆序恰好是「左右根」
三种后序迭代写法的对比（这是本节最值钱的取舍）：
| 写法 | 原理 | 代码量 | Python 速度 |
|---|---|---|---|
「根右左」+ reverse() |
先序模板对换左右，最后反转 | 最短 | ✅ 最快（reverse 在 C 层） |
| 双栈法 | 一个栈做「根右左」，另一个栈收集 | 中 | ⚠️ 多一个栈的 append/pop |
标记法 (u, visited) |
栈里存二元组，第二次遇到才访问 | 长 | ❌ 每个点造一个元组，慢 2 倍 |
为什么「根右左 + 反转」是对的：「根右左」的逆序是「左右根」—— 逆序会把「根在最前」变成「根在最后」，同时把「右在左前」变成「左在右前」， 正好是后序。一分钟就能在三节点的树上手验。
层序遍历¶
层序（BFS）就是 94.4 的 order，一个列表当队列即可：
# [片段] 层序遍历
out = [root] # 结果和队列合二为一
for u in out: # 列表在迭代中扩展是安全的
if left[u]: # 队列只在尾部追加、指针只往前走，
out.append(left[u]) # 所以 for 的内部游标不会失效
if right[u]:
out.append(right[u]) # 先左后右 -> 同层内保持左右次序
由遍历序列重建二叉树¶
| 已知 | 能唯一重建吗 | 原因 |
|---|---|---|
| 先序 + 中序 | ✅ | 先序首元素是根，在中序里定位它 ⟹ 左右子树的规模确定 |
| 后序 + 中序 | ✅ | 后序末元素是根，同理 |
| 层序 + 中序 | ✅ | 同理 |
| 先序 + 后序 | ❌ | 无法区分「只有左孩子」和「只有右孩子」 |
| 单独任一种 | ❌ | 显然 |
中序是重建的关键：只有中序能把「根左边」和「根右边」切开。 实现时把中序的「值 → 下标」预处理成
dict， 否则每层都要list.index扫一遍，退化成 \(O(n^2)\)。
94.4 「reversed(BFS 序) 就是后序」¶
这是 Python 里写树上 DP 的标准姿势，重要程度不亚于任何一个模板。
BFS 序里，父亲一定排在所有儿子之前。 所以倒着遍历 BFS 序，就等价于「所有儿子都处理完之后再处理父亲」—— 也就是后序 / 自底向上。
def bfs_order(n, start, adj, root=1):
"""求 BFS 序与父亲数组（CSR 存图）。O(n)，无递归、无栈、无 deque。
order 里父亲一定排在儿子前面，因此 reversed(order) 就是一个合法后序。
★ `for u in order:` 一边迭代一边 append —— BFS 只在尾部追加，安全。
"""
par = [0] * (n + 1) # par[root] = 0，0 号点当「没有父亲」的哨兵
vis = bytearray(n + 1)
vis[root] = 1
order = [root] # 结果和队列合二为一
for u in order:
for i in range(start[u], start[u + 1]):
v = adj[i]
if not vis[v]: # 树上唯一的「回头路」就是父亲
vis[v] = 1
par[v] = u # 建立父子关系，无根树就此定向
order.append(v)
return order, par
def subtree_size(n, order, par):
"""子树大小。倒着扫一遍 BFS 序即可，O(n)。"""
sz = [1] * (n + 1) # 每个点先把自己算 1
for u in reversed(order): # ★ 儿子一定已经算完
p = par[u]
if p: # 根的 par 是 0，到根就不再往上累加
sz[p] += sz[u] # 把自己整棵子树的规模并给父亲
return sz
| 三种「自底向上」写法 | 深度限制 | 速度 | 评价 |
|---|---|---|---|
| 递归 DFS | ❌ \(n \ge 1000\) 爆栈 | 慢 | 只能写小数据 |
迭代 DFS + (u, leaving) 事件栈 |
✅ | 中（每点一个元组） | 需要「进入/离开」两个时机时才用 |
| BFS 序倒序 | ✅ | 最快（两个纯数组循环） | ✅ 树上 DP 的默认写法 |
它能做什么：子树大小、子树权值和、树形 DP（没有上司的舞会、树上背包）、 树上差分的「子树求和」收尾、直径的树形 DP…… 凡是「先算儿子再算父亲」的都能用。见 60.4 与 103-区间树形状压DP。
它不能做什么：子树区间。BFS 序里一棵子树的点不连续， 要连续区间必须用 DFS 先序（94.5）。
94.5 DFS 序与子树区间¶
三种「序」必须分清¶
| 名称 | 长度 | 每个点出现几次 | 核心性质 | 主要用途 |
|---|---|---|---|---|
DFS 序 / 先序 / dfn |
\(n\) | 1 次（进入时） | 子树 = 连续区间 | 子树改 → 区间改 |
| 括号序 | \(2n\) | 2 次（进入 + 离开） | 祖先关系 = 括号嵌套 | 判祖先、树上莫队 |
| 欧拉序 | \(2n-1\) | \(\deg\) 次（每次回溯都记） | 两点间必经过 LCA | LCA → RMQ（94.9） |
⚠️ 这三个名字在不同资料里混用得很厉害，看到「DFS 序」时一定确认长度： 长度 \(n\) 是先序，\(2n\) 是括号序，\(2n-1\) 是欧拉序。 LCA 用的是欧拉序（\(2n-1\)），这是最容易搞错的一处。
DFS 先序与子树区间¶
def dfs_order(n, start, adj, root=1):
"""DFS 先序（迭代）与子树大小。O(n)。返回 (tin, sz, seq, par)。
tin[u] = u 在先序里的下标（0-indexed），seq[tin[u]] == u。
★ 关键性质：子树 u 恰好对应连续区间 [tin[u], tin[u] + sz[u] - 1]。
因为栈式先序会把 u 的整棵子树连续地弹出。
"""
par = [0] * (n + 1)
tin = [0] * (n + 1)
seq = [] # seq = 先序序列本身
vis = bytearray(n + 1)
vis[root] = 1
st = [root]
while st:
u = st.pop() # 栈顶 = 最近压入 -> 优先往深处走
tin[u] = len(seq) # 当前长度就是 u 的先序下标
seq.append(u)
for i in range(start[u], start[u + 1]):
v = adj[i]
if not vis[v]:
vis[v] = 1 # 入栈即标记，同一点不会被压两次
par[v] = u
st.append(v)
sz = [1] * (n + 1)
for u in reversed(seq): # 先序倒序 = 后序
p = par[u]
if p:
sz[p] += sz[u]
return tin, sz, seq, par
def is_ancestor(u, v, tin, sz):
"""u 是否是 v 的祖先（含 u == v）。O(1)。"""
# u 的子树占据先序区间 [tin[u], tin[u]+sz[u])，v 落在里面就是它的后代
return tin[u] <= tin[v] < tin[u] + sz[u]
子树区间这条性质把「树上问题」变成了「序列问题」：
| 树上操作 | 序列操作 | 用什么 |
|---|---|---|
| 子树 \(u\) 整体加 \(k\) | 区间 \([tin_u,\ tin_u+sz_u-1]\) 加 \(k\) | 树状数组 / 线段树（39 章） |
| 查询子树 \(u\) 的权值和 | 区间求和 | 同上 |
| 单点改 + 子树查 | 单点改 + 区间查 | 树状数组 |
| 路径操作 | ⚠️ 不能直接映射 | 需要树链剖分（113 章） |
「子树 = 区间」很容易，「路径 = 区间」很难，这就是树链剖分存在的理由： 它把每条路径拆成 \(O(\log n)\) 段连续区间。 树剖的
id[u]同时也是一种 DFS 序，所以子树操作和路径操作能共用同一棵数据结构。
94.6 树的直径¶
直径：树上最长的简单路径（的长度）。
做法一：两次 BFS（无权树 / 非负权）¶
从任意点出发 BFS，找到最远点 \(a\)；再从 \(a\) 出发 BFS，找到最远点 \(b\)。 则 \(a \to b\) 就是一条直径。
def tree_diameter_bfs(n, start, adj):
"""两次 BFS 求树的直径（无权树）。返回 (直径边数, 端点 a, 端点 b)。O(n)。
⚠️ 正确性依赖「边权非负」。有负权边时这个结论不成立，必须用树形 DP。
"""
def farthest(s):
"""从 s 出发 BFS，返回 (最远点, 该距离)。"""
dist = [-1] * (n + 1) # -1 兼任未访问标记
dist[s] = 0
q = [s] # 列表当队列：BFS 只在尾部追加
for u in q:
d = dist[u] + 1
for i in range(start[u], start[u + 1]):
v = adj[i]
if dist[v] < 0: # 树上不需要父亲判断，标记就够
dist[v] = d
q.append(v)
m = max(dist) # ★ max / index 都在 C 层
return dist.index(m), m # 有并列时取下标最小的，任选一个都对
a, _ = farthest(1) # 第一次：从任意点找到一个直径端点 a
b, d = farthest(a) # 第二次：从 a 出发，最远点就是另一端 b
return d, a, b
正确性证明（反证）：设真正的直径是 \((s,t)\)，从任意点 \(x\) 出发的最远点是 \(a\)。 若 \(a\) 不是任何直径的端点，考察 \(x \to a\) 与 \(s \to t\) 这两条路径：
- 若它们相交于点 \(p\)，则 \(d(p,a) \ge d(p,s)\)（否则 \(x\to s\) 比 \(x\to a\) 更远）， 于是把 \(s\) 换成 \(a\) 得到的路径不比直径短，矛盾（\(a\) 也是直径端点）；
- 若它们不相交，设连接两条路径的最短路是 \(p\to q\)（\(p\) 在 \(x\to a\) 上，\(q\) 在 \(s\to t\) 上）， 则 \(d(p,a) \ge d(p,q)+d(q,s)\)，于是 \(d(a,t) = d(a,p)+d(p,q)+d(q,t) \ge d(s,q)+d(q,t) = d(s,t)\)， 同样说明 \(a\) 是直径端点。
⚠️ 有负权边时两次 BFS 就是错的（上面的不等式全部依赖非负性）。 竞赛里「树的直径 + 负权」不算罕见，看到负权立刻换树形 DP。
做法二：树形 DP（边权可负）¶
对每个点 \(u\)，「经过 \(u\) 的最长路径」= \(u\) 向下的最长链 + 次长链：
def tree_diameter_dp(n, start, adj, wt=None, root=1):
"""树形 DP 求直径（边权可为负）。O(n)。用 BFS 序倒序代替递归。
down[u] = 从 u 向下走的最长链长度（允许长度 0，即停在 u）。
技巧：处理 u 的每个孩子 v 时，down[u] 里存的是「已处理过的孩子中的最长」，
所以 down[u] + (down[v] + w) 就是「次长 + 最长」，
★ 先更新答案，再更新 down[u]，一趟就同时拿到最长和次长。
"""
order, par = bfs_order(n, start, adj, root)
down = [0] * (n + 1) # 初值 0 = 「停在 u 不往下走」也是合法的链
best = 0
for u in reversed(order): # 倒序 = 后序，孩子的 down 已经是终值
du = down[u] # 局部变量累积，最后一次性写回
for i in range(start[u], start[u + 1]):
v = adj[i]
if v == par[u]:
continue # 树上不走回父亲，就等于只看孩子
cand = down[v] + (1 if wt is None else wt[i]) # 经 v 往下的链长
if du + cand > best: # ★ 先算答案（此时 du 是次长候选）
best = du + cand # du 来自之前的孩子，与 cand 分属两个方向
if cand > du: # 再更新最长
du = cand
down[u] = du
return best # 答案是「经过某个点的最长路径」的最大值
| 两次 BFS | 树形 DP | |
|---|---|---|
| 复杂度 | \(O(n)\)（两遍） | \(O(n)\)（一遍） |
| 负权边 | ❌ 不正确 | ✅ |
| 能得到直径的端点 | ✅ 直接给出 | ⚠️ 要额外记录 |
| 代码量 | 短 | 中 |
| Python 常数 | 小（两次纯 BFS） | 小 |
| 顺便求「每点的最远距离」 | ⚠️ 要两遍 BFS 后取 max | ✅ 换根 DP 一并求出 |
默认选两次 BFS：更短、更好写、端点直接拿到。 只有出现负权或需要「每个点的最长链」时才上树形 DP。
94.7 树的重心与树的中心¶
这两个概念长得像，完全不是一回事：
| 重心（centroid） | 中心（center） | |
|---|---|---|
| 定义 | 删掉它后，最大子树的点数最小 | 到最远点的距离最小 |
| 等价刻画 | 使 \(\sum_v d(u,v)\) 最小的点 | 直径的中点 |
| 个数 | 1 个或 2 个（相邻） | 1 个或 2 个（相邻） |
| 求法 | 一遍求 sz，再扫一遍 |
求出直径路径，取中点 |
| 主要用途 | 点分治、树的平衡分解 | 「最小化最远距离」类题 |
def tree_centroid(n, start, adj, order, par, sz):
"""树的重心：删掉它后最大连通块的点数最小。返回 (重心, 该最小值)。O(n)。
删掉 u 之后的连通块有两类：
- 每个孩子 v 的子树，大小 sz[v]；
- 「父亲那一侧」，大小 n - sz[u]。
"""
best_node = 1
best_val = n + 1 # 比任何可能的块大小都大，保证首轮被刷新
for u in range(1, n + 1):
mx = n - sz[u] # ★ 父亲那一侧：总点数减去 u 的子树
# u 是根时它等于 0，天然正确
for i in range(start[u], start[u + 1]):
v = adj[i]
if v != par[u] and sz[v] > mx: # 跳过父亲，其余邻居都是孩子
mx = sz[v] # mx = 删掉 u 后最大的那块
if mx < best_val:
best_val = mx
best_node = u
return best_node, best_val # best_val <= n//2 是重心的特征性质
重心的性质（点分治的正确性来源）：
| 性质 | 说明 |
|---|---|
| 最大子树大小 \(\le \lfloor n/2 \rfloor\) | 所以点分治的递归深度是 \(O(\log n)\) |
| 以重心为根时，所有子树大小 \(\le n/2\) | 同上 |
| 重心到所有点的距离和最小 | 「选一个点使总距离最小」直接找重心 |
| 两棵树合并后，新重心在原两个重心的路径上 | 增量维护重心 |
| 有两个重心 ⟺ 存在一条边把树分成两个 \(n/2\) | \(n\) 必为偶数 |
BISHI101「从所有叶子出发的多源 BFS」求的是「到最近叶子距离最大的点」， 那个点集与树的中心有关但并不相同——它是「内部深度」的最大点。 见 61-BFS广度优先搜索。
94.8 树上两点路径长度¶
有了 LCA，路径长度就是一个减法：
为什么减两倍：\(u \to \text{root}\) 和 \(v \to \text{root}\) 这两条路径在 LCA 上方完全重合，重合部分被算了两次，要减掉两次。
| 需求 | 公式 |
|---|---|
| 路径边数（无权） | \(\mathrm{dep}[u]+\mathrm{dep}[v]-2\mathrm{dep}[l]\) |
| 路径权值和（带权） | \(D[u]+D[v]-2D[l]\)，\(D\) 是根到该点的权和 |
| 路径异或和 | \(X[u] \oplus X[v]\)（不用减！异或自己抵消，见 73.5） |
| 路径点数 | 边数 \(+1\) |
| 判 \(w\) 是否在路径 \(u\to v\) 上 | \(\mathrm{dist}(u,w)+\mathrm{dist}(w,v) = \mathrm{dist}(u,v)\) |
| 路径的中点 | 从深的那端向上跳 \(\lfloor \mathrm{dist}/2 \rfloor\) 步（倍增求 \(k\) 级祖先） |
树上差分：给路径 \(u\to v\) 上所有点加 \(k\)，只在 4 个点打标记，最后一次子树求和：
| 类型 | 标记 |
|---|---|
| 点差分 | \(d_u\mathrel{+}=k\)，\(d_v\mathrel{+}=k\)，\(d_{l}\mathrel{-}=k\)，\(d_{par(l)}\mathrel{-}=k\) |
| 边差分 | \(d_u\mathrel{+}=k\)，\(d_v\mathrel{+}=k\)，\(d_{l}\mathrel{-}=2k\) |
收尾的「子树求和」正是 94.4 的 reversed(order) 一趟循环。
完整讨论见 42.6。
94.9 最近公共祖先（LCA）¶
LCA\((u,v)\)：既是 \(u\) 的祖先又是 \(v\) 的祖先中深度最大的那个点。
三条主流路线，Python 下的取舍和 C++ 完全不同。
路线一：倍增（通用首选）¶
\(fa_j[v]\) = \(v\) 向上跳 \(2^j\) 步的祖先，\(fa_j[v] = fa_{j-1}[fa_{j-1}[v]]\)。
def build_lca_lifting(n, start, adj, root):
"""倍增 LCA 预处理。O(n log n)。返回 (dep, fa, LOG, order)。
0 号点当哨兵（fa[*][0] = 0），跳出树顶自动停在 0，查询里不用写边界判断。
"""
LOG = max(1, n.bit_length()) # 跳 2^(LOG-1) 步已经超过树高，够用
dep = [0] * (n + 1) # dep[0] = 0 是哨兵；根的深度设为 1
# 根不取 0，是为了让 dep == 0 能当未访问标记
fa = [[0] * (n + 1) for _ in range(LOG)] # fa[j][v] = v 向上 2^j 步的祖先
f0 = fa[0] # 第 0 层就是直接父亲
dep[root] = 1
order = [root]
for u in order: # BFS 求深度与父亲，不用递归
du = dep[u] + 1
for i in range(start[u], start[u + 1]):
v = adj[i]
if dep[v] == 0: # dep 兼任访问标记
dep[v] = du
f0[v] = u
order.append(v)
for j in range(1, LOG): # 倍增递推：跳 2^j 步 = 连跳两次 2^(j-1) 步
prev = fa[j - 1]
fa[j] = [prev[prev[v]] for v in range(n + 1)] # ★ 整层列表推导，C 层循环
# 跳出树顶的点会落到 0，并一直停在 0
return dep, fa, LOG, order
def lca_lifting(x, y, dep, fa, LOG):
"""倍增查询 LCA。O(log n)。"""
if dep[x] < dep[y]:
x, y = y, x # 统一成「x 更深」，后面只往上提 x
d = dep[x] - dep[y] # 要提升的层数
j = 0
while d: # ① 把深的那个提到同一层
if d & 1: # d 的二进制第 j 位为 1 -> 跳 2^j 步
x = fa[j][x] # 层差被拆成若干个 2 的幂，共跳 O(log n) 次
d >>= 1
j += 1
if x == y: # ★ 必须先判：y 可能本来就是 x 的祖先
return x
for j in range(LOG - 1, -1, -1): # ② 一起上跳：跳完仍不同才跳
if fa[j][x] != fa[j][y]: # 相等说明跳过头了（越过了 LCA），不跳
x = fa[j][x] # 从大步长到小步长，逼近「最深的非公共祖先」
y = fa[j][y]
return fa[0][x] # 此时两者的父亲就是 LCA
⚠️ 第二个循环是「不同才跳」。我们要找「最深的、仍然不是公共祖先的位置」； 若 \(fa_j[x] = fa_j[y]\) 说明跳过头了。 写成
if fa[j][x] == fa[j][y]: x = fa[j][x]是最常见的错法。⚠️
x == y一定要在第二个循环之前判。若 \(y\) 本来就是 \(x\) 的祖先， 提到同层后两者已相等，此时进第二个循环会返回fa[0][x]（多跳一层），答案偏浅。
倍增的通用讨论（快速幂、ST 表、序列倍增）见 45-倍增。
路线二：Tarjan 离线¶
思想：一遍 DFS，用并查集把「已经回溯完的子树」合并到父亲上。 DFS 到 \(u\) 时，若询问 \((u,v)\) 的 \(v\) 已经访问过，则 \(\mathrm{lca} = \mathrm{find}(v)\)。
# [片段] Tarjan 离线 LCA 的骨架（需配迭代 DFS）
# 1) 把所有询问挂到两个端点上：qry[u].append((v, 询问编号))
# 2) 迭代 DFS：
# 进入 u：vis[u] = 1
# 离开 u 的每个孩子 v 之后：parent[v] = u （并查集合并到父亲）
# 处理 u 时：对 qry[u] 里每个 (v, id)，若 vis[v]: ans[id] = find(v)
# 3) 关键点：合并必须发生在「孩子子树完全处理完」之后，
# 所以需要「进入 / 离开」两个时机 -> 事件栈式迭代 DFS（见 90.5 模板二）
| Tarjan 离线 | 评价 |
|---|---|
| 复杂度 | \(O((n+q)\,\alpha(n))\)，理论最优 |
| 要求 | 必须离线（所有询问预先给出） |
| Python 现实性 | ⚠️ 需要事件栈式迭代 DFS + 把 \(q\) 个询问挂到点上，常数不小；\(n,q \le 10^5\) 可行，\(5\times10^5\) 很吃力 |
| 代码量 | 最大（迭代 DFS + 并查集 + 挂询问） |
路线三：欧拉序 + ST 表（Python 下最快）¶
核心归约：
对树做欧拉序（DFS 进入时记一次，每次从孩子回溯回来也记一次，长度恰好 \(2n-1\)）， 则 $\mathrm{lca}(u,v) = $ 欧拉序区间 \([\mathrm{first}[u],\ \mathrm{first}[v]]\) 里深度最小的那个点。
为什么：从 \(u\) 走到 \(v\) 的这段欧拉序必然经过它们的 LCA（要出这棵子树只能从 LCA 走）， 而且不会走到比 LCA 更浅的地方（那要先离开 LCA 的子树，与 \(v\) 在子树内矛盾）。
于是 LCA 变成了 RMQ（Range Minimum Query，区间最值查询：给定数组和一个区间， 问区间内的最小值）。RMQ 可以用 ST 表（Sparse Table，稀疏表：预处理所有 「起点 \(i\)、长度 \(2^j\)」的区间最值）做到 \(O(1)\) 查询，见 45-倍增。
编码技巧：把 \((\text{深度},\ \text{点号})\) 压进一个整数 dep << 20 | node
（要求 \(n < 2^{20} = 1048576\)）。这样：
- 比较大小就是比较整数，可以直接用内置
min； - ST 表建表能写成
list(map(min, prev, prev[h:]))，整层比较全在 C 层； - 取到最小值后
& 0xFFFFF就是 LCA 的点号。 - 区间里深度最小的点唯一（就是 LCA），所以不会有并列歧义。
def build_lca_euler(n, start, adj, root, SH=20):
"""欧拉序 + ST 表 LCA。预处理 O(n log n)，查询 O(1)。
欧拉序长度 2n-1；元素是 (dep << SH) | node，可直接用 min 比较。
要求 n < 2^SH。迭代式 DFS，n = 5e5 也不会爆栈。
"""
par = [0] * (n + 1)
ptr = start[:] # 每个点扫到邻接表的哪里了
# 这就是「手工保存的循环变量」，代替递归现场
first = [0] * (n + 1) # first[u] = u 在欧拉序里首次出现的下标
euler = []
push = euler.append
dep = 0 # 当前栈顶的深度，随进出栈同步升降
stk = [root]
first[root] = 0
push(root) # (0 << SH) | root，根的深度是 0
while stk:
u = stk[-1] # 只看栈顶，不弹出：它的孩子可能还没走完
p = ptr[u]
if p < start[u + 1]: # u 还有没访问过的邻居
ptr[u] = p + 1 # 游标右移，下次从后一个邻居继续
v = adj[p]
if v != par[u]: # 树上不需要 vis，只要不走回父亲
par[v] = u
dep += 1
first[v] = len(euler) # 记下 v 首次出现的位置
push((dep << SH) | v)
stk.append(v) # 下潜一层
else:
stk.pop() # u 的邻居扫完了，回溯
dep -= 1
if stk:
push((dep << SH) | stk[-1]) # ★ 回溯到父亲，再记一次
# 这一步让欧拉序长度成为 2n-1
# ---- ST 表（Sparse Table，稀疏表）：st[j][i] = 从 i 开始 2^j 个元素的最小值 ----
st = [euler] # 第 0 层就是欧拉序本身（区间长度 1）
L = len(euler)
j = 1
while (1 << j) <= L:
prev = st[-1]
h = 1 << (j - 1) # 上一层的区间长度
st.append(list(map(min, prev, prev[h:]))) # ★ 整层一次算完，全在 C 层
# 两个错开 h 的半区间取 min 即得本层
j += 1
return first, st
def lca_euler(u, v, first, st, SH=20):
"""O(1) 查询 LCA。"""
l = first[u]
r = first[v]
if l > r:
l, r = r, l # 保证 l <= r，区间才有意义
k = (r - l + 1).bit_length() - 1 # ⌊log2(len)⌋
row = st[k]
a = row[l] # 从左端起的 2^k 个
b = row[r - (1 << k) + 1] # 到右端为止的 2^k 个；两段重叠但不影响取 min
return (a if a < b else b) & ((1 << SH) - 1) # 低位掩码还原出点号
list(map(min, prev, prev[h:]))是这条路线在 Python 下取胜的唯一原因。map遇到较短的可迭代对象就停止，正好得到长度 \(L-2^j+1\) 的新层， 而整层的 \(L\) 次比较全部在 C 层完成。 手写for i in range(...)要慢 5–10 倍。同一个技巧见 45.2 ST 表。
内存问题：\(n\) 很大时 ST 表放不下¶
欧拉序长 \(2n-1\)。\(n = 5\times10^5\) 时 \(L \approx 10^6\)，
ST 表有 \(\lceil\log_2 L\rceil = 20\) 层，共 \(2\times10^7\) 个元素——
Python 的 list 存这些非缓存整数要 150 MB 以上，建表也要好几秒。
解法：分块 + 只对块间建 ST 表。
| 朴素 ST 表 | 分块 + 块间 ST 表 | |
|---|---|---|
| 块长 \(B\) | 1 | 64 |
| 表的元素数 | \(L\log L \approx 2\times10^7\) | \(\dfrac{L}{B}\log\dfrac{L}{B} \approx 2\times10^5\)（降两个数量级） |
| 查询 | 2 次表访问 | 两端零散部分 min(切片)（C 层扫 \(\le 64\) 个）+ 中间整块查表 |
| 查询复杂度 | \(O(1)\) | \(O(B)\) 但常数极小（切片 min 在 C 层） |
这正是 BISHI124 题解采用的结构，完整代码见 94.11。
三条路线的对比¶
| 倍增 | Tarjan 离线 | 欧拉序 + ST 表 | |
|---|---|---|---|
| 预处理 | \(O(n\log n)\) | \(O(n\,\alpha)\) | \(O(n\log n)\) |
| 单次查询 | \(O(\log n)\) | 均摊 \(O(\alpha)\) | \(O(1)\) |
| 在线？ | ✅ | ❌ 必须离线 | ✅ |
| 顺便能求 \(k\) 级祖先 / 路径最值 | ✅ 只有倍增能 | ❌ | ❌ |
| 预处理的 Python 层操作量 | \(n\log n\) 次（列表推导，半 C 层） | \(O(n+q)\) 次（纯 Python） | \(L\) 次 DFS + 建表全 C 层 |
| 查询的 Python 层操作量 | \(q\log n\) 次（纯 Python，最贵） | \(O(q\,\alpha)\) | \(q \times\) 常数 |
| 代码量 | 中 | 大 | 中 |
| Python 推荐场景 | \(n,q \le 2\times10^5\)；或需要 \(k\) 级祖先 / 路径最值 | 很少（常数不划算） | \(q\) 很大时唯一现实的路线 |
| 规模（\(n \approx q\)） | 倍增 | 欧拉序 + ST 表 |
|---|---|---|
| \(10^5\) | ✅ 约 1–2 s | ✅ 约 1 s |
| \(2\times10^5\) | ⚠️ 约 3–4 s | ✅ 约 1.5–2 s |
| \(5\times10^5\) | ❌ 建表 \(10^7\) + 查询 \(10^7\) 次 Python 层操作 | ⚠️ 仍然很险（见 BISHI124） |
一句话决策： 查询次数少（\(q \le 10^5\)）或需要「跳 \(k\) 步」→ 倍增； 查询次数极大（\(q \ge 3\times10^5\)）→ 欧拉序 + 分块 ST 表。 Tarjan 在 C++ 里是最优解，在 Python 里几乎从不划算。
94.10 树链剖分预告¶
到这里，「子树操作」已经能用 DFS 序 + 数据结构解决（94.5）， 「路径查询」能用 LCA 解决（94.8、94.9）。 剩下唯一没解决的是路径上的修改与聚合查询：
「把路径 \(u \to v\) 上所有点加 \(k\)」「查询路径 \(u\to v\) 上的最大值」
重链剖分把每条路径拆成 \(O(\log n)\) 段连续区间，
配一棵线段树就能做到 \(O(\log^2 n)\)。它的 id[u] 同时也是 DFS 序，
所以子树操作和路径操作共用同一棵数据结构。
完整讲解见 113-树链剖分。 那里也会诚实地讨论 Python 的可行规模—— 懒标记线段树在 CPython 下 \(10^5\) 量级就已经很险（见 39 章）， 所以树剖题在 Python 下的现实上界比 C++ 低一个数量级。
94.11 例题¶
BISHI96 先序遍历、中序遍历和后序遍历（简单）¶
给定 \(n\ (\le 10^5)\) 个节点的二叉树，以 \(n-1\) 条有向边 \((a_i,b_i)\) 给出 （父 \(a_i\) 指向子 \(b_i\)）。左右关系的规定是： - 父节点有两个孩子 ⟹ 编号较小者为左孩子，较大者为右孩子； - 父节点只有一个孩子，且该孩子编号大于父节点编号 ⟹ 视为左孩子；否则为右孩子。
输出先序、中序、后序遍历序列。 题面见 BISHI96 原题（牛客）。 题解见
solutions/BISHI96.py（已通过官方样例验证）。
这题的难点全在两处：左右孩子的规则，和 \(n = 10^5\) 的递归深度。
先把规则整理成表（读错这张表就全错，且样例查不出来）：
| 情况 | 左孩子 | 右孩子 |
|---|---|---|
| 两个孩子 \(x < y\) | \(x\)（小的在左） | \(y\) |
| 一个孩子 \(v\)，且 \(v > u\) | \(v\) | 空 |
| 一个孩子 \(v\)，且 \(v < u\) | 空 | \(v\) |
⚠️ 判定基准是「孩子编号 vs 父节点编号」，不是「孩子编号 vs 兄弟」， 也不是「独子固定放左边」。两个孩子时比的是兄弟之间， 一个孩子时比的是和父亲——两条规则的比较对象不同，这是本题唯一的阅读陷阱。
根 = 入度为 0 的点（没有出现在任何 \(b_i\) 里）。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
left = [0] * (n + 1) # 0 表示空，别用节点类
right = [0] * (n + 1)
kids = [[] for _ in range(n + 1)]
has_parent = bytearray(n + 1) # 用来找根
p = 1
for _ in range(n - 1):
a = int(data[p]); b = int(data[p + 1]); p += 2
kids[a].append(b)
has_parent[b] = 1
for u in range(1, n + 1): # ---- 按规则定左右 ----
ch = kids[u]
if len(ch) == 2:
x, y = ch
if x > y:
x, y = y, x
left[u], right[u] = x, y # 两个孩子：小的在左
elif len(ch) == 1:
v = ch[0]
if v > u:
left[u] = v # 独子且编号 > 父 -> 左
else:
right[u] = v # 否则 -> 右
root = 1
for u in range(1, n + 1): # 入度为 0 的点就是根
if not has_parent[u]:
root = u
break
# ---- 先序：根 左 右（栈里先压右再压左）----
pre = []
st = [root]
while st:
u = st.pop()
pre.append(u)
r = right[u]
if r:
st.append(r)
l = left[u]
if l:
st.append(l)
# ---- 中序：一路向左压栈，弹出访问后转右子树 ----
ino = []
st = []
u = root
while st or u:
while u:
st.append(u)
u = left[u]
u = st.pop()
ino.append(u)
u = right[u]
# ---- 后序：按「根 右 左」跑先序，再整体逆序 ----
post = []
st = [root]
while st:
u = st.pop()
post.append(u)
l = left[u]
if l:
st.append(l)
r = right[u]
if r:
st.append(r)
post.reverse() # ★ 一次 C 层反转
w = sys.stdout.write
w(" ".join(map(str, pre)) + "\n")
w(" ".join(map(str, ino)) + "\n")
w(" ".join(map(str, post)) + "\n")
main()
复杂度：建树 \(O(n)\)，三次遍历各 \(O(n)\)。\(n = 10^5\) 瞬间完成。
样例复核（这类题一定要手验）：\(n=2\)，边 \(1\to2\)。 父 1 只有一个孩子 2，且 \(2 > 1\) ⟹ 左孩子。 先序 \(=1\ 2\)；中序 \(=\) 左(2) 根(1) \(= 2\ 1\)；后序 \(=\) 左(2) 根(1) \(= 2\ 1\)。与样例一致 ✓
四个坑：
- 三种遍历全部必须迭代。这棵树可以是 \(1\to2\to\cdots\to10^5\) 的链，
递归深度 \(10^5\)；即使
setrecursionlimit调大，C 栈也会崩（无报错的段错误）； - 独子的判定基准是父节点编号（见上面的阅读陷阱）；
- \(n = 1\) 时没有任何边，
kids全空、has_parent全 0， 根取到 1，三行都输出1。代码天然处理，但一定要在脑子里跑一遍； - 输出必须先
join再一次write。三行各 \(10^5\) 个数， 逐个print会有 \(3\times10^5\) 次系统调用级开销 （20-输入输出处理）。
为什么后序用「根右左 + reverse」而不是双栈：见 94.3 的对比表。 一次 C 层
list.reverse()比多维护一个栈快，代码也短 5 行。 同一份代码，三个遍历只差左右压栈顺序和一次反转——这是本题最优雅的地方。
BISHI124 【模板】最近公共祖先（LCA）（中等）¶
给定 \(N\) 个点、以 \(R\) 为根的多叉树，\(M\) 次询问两点的 LCA。 \(1 \le R \le N \le 5\times10^5\)，\(1 \le M \le 5\times10^5\)。 树以 \(N-1\) 条无向边 \((x,y)\) 给出（只表示相连，方向要靠 \(R\) 定）。 时限：C/C++ 3 秒，其他语言 6 秒；空间：其他语言 512 MB。 题面见 BISHI124 原题（牛客）。 题解见
solutions/BISHI124.py（已通过官方样例验证）。
第一步：为什么不能用倍增¶
\(N = M = 5\times10^5\)，\(\log_2 N = 19\)：
| 阶段 | Python 层操作量 |
|---|---|
| 倍增建表 \(19 \times 5\times10^5\) | \(\approx 10^7\) 次（列表推导，约 3–5 s） |
| \(5\times10^5\) 次查询 \(\times\) 约 20 次跳跃 | \(\approx 10^7\) 次（纯 Python 循环，约 8–12 s） |
| 内存：19 层 \(\times\) \(5\times10^5\) | \(10^7\) 个列表槽，约 80 MB 指针 + 整数对象 |
总计 \(2\times10^7\) 次 Python 层操作，时限只有 6 秒——必挂。 45 章 给出的倍增模板在这个规模上确实过不去， 所以本章承担「替代路线」这部分。
第二步：欧拉序 + 分块 ST 表¶
按 94.9 路线三：欧拉序把 LCA 归约成 RMQ，查询降到 \(O(1)\)； 再用「分块 + 块间 ST 表」把表的规模从 \(2\times10^7\) 降到 \(2\times10^5\)。
import sys
def main():
data = sys.stdin.buffer.read().split()
N = int(data[0]); M = int(data[1]); R = int(data[2])
# ---- CSR 邻接表：deg 前缀和 + 一次填充（5e5 个小 list 的内存扛不住）----
ne = 2 * (N - 1)
es = list(map(int, data[3:3 + ne])) # 只解析一次，别在两个循环里各 int() 一遍
deg = [0] * (N + 2)
for x in es:
deg[x] += 1
start = [0] * (N + 2)
acc = 0
for v in range(1, N + 1):
start[v] = acc
acc += deg[v]
start[N + 1] = acc
pos = start[:]
adj = [0] * acc
for i in range(0, ne, 2):
x = es[i]; y = es[i + 1]
adj[pos[x]] = y; pos[x] += 1
adj[pos[y]] = x; pos[y] += 1
# ---- 迭代式 DFS 生成欧拉序（元素 = dep << 20 | node）----
par = [0] * (N + 1)
ptr = start[:] # 每个点当前扫到邻接表的哪里
euler = []
push = euler.append
first = [0] * (N + 1)
dep = 0
stk = [R]
par[R] = 0
first[R] = 0
push(R) # dep = 0
while stk:
u = stk[-1]
p = ptr[u]
if p < start[u + 1]:
ptr[u] = p + 1
v = adj[p]
if v != par[u]: # 树上不需要 vis，不走回父亲即可
par[v] = u
dep += 1
first[v] = len(euler)
push((dep << 20) | v)
stk.append(v)
else:
stk.pop()
dep -= 1
if stk:
push((dep << 20) | stk[-1]) # 回溯，再记一次父亲
L = len(euler)
# ---- 分块 + 块间稀疏表：块长 64，表只有 14 * 1.6e4 ≈ 2e5 个元素 ----
B = 64
nb = (L + B - 1) // B
blk = [min(euler[b * B:(b + 1) * B]) for b in range(nb)] # 每块最小值，C 层
st = [blk]
j = 1
while (1 << j) <= nb:
prev = st[-1]
h = 1 << (j - 1)
st.append(list(map(min, prev, prev[h:]))) # ★ 整层 C 层建表
j += 1
p = 3 + ne
out = []
push = out.append
MASK = (1 << 20) - 1
for _ in range(M):
a = int(data[p]); b = int(data[p + 1])
p += 2
l = first[a]; r = first[b]
if l > r:
l, r = r, l
bl = l // B
br = r // B
if bl == br: # 同一块内：直接 C 层扫 <= 64 个
v = min(euler[l:r + 1])
else:
v = min(euler[l:(bl + 1) * B]) # 左端零散部分
w = min(euler[br * B:r + 1]) # 右端零散部分
if w < v:
v = w
if br - bl > 1: # 中间的整块查稀疏表
k = (br - bl - 1).bit_length() - 1
row = st[k]
x = row[bl + 1]
y = row[br - (1 << k)]
if x < v:
v = x
if y < v:
v = y
push(v & MASK) # 取回点号
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()
复杂度：预处理 \(O(N)\)（DFS + 分块）\(+\ O(n_b\log n_b)\)（块间 ST 表），
查询 \(O(1)\)（两次 C 层切片 min + 两次表访问）。
第三步：诚实的可行性判断¶
⚠️ 本题在 CPython 3.9 下大概率 TLE，即使用上了上面这套「理论最优」的做法：
阶段 Python 层操作量 读入 \(2\times5\times10^5 + 2\times5\times10^5 = 2\times10^6\) 个 token 并 int()\(\ge 1\) s 建 CSR（度数 + 前缀和 + 填充） \(\approx 2\times10^6\) 次 迭代 DFS 生成欧拉序（\(10^6\) 个元素，每个要 push / 判父亲） \(\approx 1.5\times10^6\) 次 \(5\times10^5\) 次查询 \(\times\)（约 10 次 Python 层操作 + 2 次 C 层切片 min）\(\approx 5\times10^6\) 次 总量约 \(6\times10^6 \sim 8\times10^6\) 次 Python 层操作，实测在 8–15 秒量级， 而时限是「其他语言 6 秒」。
这属于「规模对 Python 不友好」，而不是做法有问题—— 预处理 \(O(N)\) + 查询 \(O(1)\) 已经是理论最优，没有更好的算法了。 换 PyPy 可过；CPython 下这题只能接受。
这题给出的三条判据：
| 判据 | 内容 |
|---|---|
| 算法选择 | \(q\) 很大时，把「查询」的复杂度压到 \(O(1)\) 比压预处理更重要。倍增的 \(q\log n\) 全是纯 Python 循环，是本题的绝对瓶颈 |
| 把循环下沉到 C 层 | list(map(min, prev, prev[h:])) 建表、min(切片) 查零散部分、list(map(int, ...)) 解析——能交给 C 的就一个字节都不留在 Python 里 |
| 内存也要算 | 朴素 ST 表 \(2\times10^7\) 个元素在 512 MB 下必 MLE；分块把它降两个数量级。「\(O(1)\) 查询」在 Python 里必须配「小表」才成立 |
四个实现坑：
- 树是无根边给出的（\(x\ y\) 只表示相连），根 \(R\) 单独给出。 必须迭代式 DFS——递归深度可达 \(5\times10^5\)；
- 欧拉序长度是 \(2N-1\)，
first[]记第一次出现的位置。 写成「最后一次」也能对，但混用就错； - 查询时若
first[u] > first[v]要交换；\(u = v\) 时区间退化成一个点，答案是自己，仍然正确； - 编码位宽：\(N \le 5\times10^5 < 2^{20}\)，所以
dep << 20 | node安全。 若 \(N\) 能到 \(2\times10^6\)，位宽要改成 21——改位宽时MASK要同步改。
本题也是 45-倍增 的例题。 分工是：45 章负责倍增模板本身（并诚实标注它在这个规模上过不去）， 本章负责「替代路线 + 为什么」。同一道题，两种算法，两层理解。
94.12 本章速查¶
树的性质与存储¶
| 要点 | 结论 |
|---|---|
| 树的定义 | 连通 + 无环 |
| 三选二定理 | 连通 / 无环 / \(m=n-1\) 任意两条 ⟹ 是树 |
| ⚠️ 只判 \(m=n-1\) | 不够，必须配连通性 |
| 任意两点 | 有唯一简单路径 |
| 加一条非树边 | 恰好产生一个环 |
| 度数和 | \(2(n-1)\)，平均度数 \(< 2\) |
| 树是二分图 | 无环 ⟹ 无奇环 |
| 找根 | 题目给 / 入度为 0（BISHI96）/ 随便取 1 |
| 换根 | \(sz'[u] = n - sz[v]\) |
| 二叉树存储 | left[] + right[] 两个数组，0 表示空；❌ 别用节点类 |
| 大树存储 | CSR（\(n \ge 2\times10^5\) 必用） |
遍历与序¶
| 要点 | 结论 |
|---|---|
| 三种遍历 | 先序 根左右 / 中序 左根右 / 后序 左右根 |
| 必须迭代 | 树高上界 \(= n\)，\(n \ge 1000\) 递归必爆（BISHI96 的 \(10^5\)） |
| 先序迭代 | 栈里先压右再压左 |
| 中序迭代 | 一路向左压栈 → 弹出访问 → 转右子树 |
| 后序迭代 | 按「根右左」跑先序，最后 reverse()（最短最快） |
| 后序的三种写法 | 反转法 ✅ > 双栈法 ⚠️ > 标记元组法 ❌ |
| BST 的中序 | 是有序的 |
| 重建二叉树 | 先序+中序 ✅、后序+中序 ✅、先序+后序 ❌ |
reversed(BFS 序) = 后序 |
树上 DP 的 Python 标准姿势，无递归无栈 |
| DFS 序（先序） | 长 \(n\)；子树 = 连续区间 \([tin_u, tin_u+sz_u-1]\) |
| 括号序 | 长 \(2n\)；判祖先、树上莫队 |
| 欧拉序 | 长 \(2n-1\)；LCA → RMQ |
| 判祖先 \(O(1)\) | tin[u] <= tin[v] < tin[u] + sz[u] |
| 子树改 → 区间改 | DFS 序 + 树状数组 / 线段树 |
| 路径改 → 区间改 | 需要树链剖分（113 章） |
| BFS 序能做子树区间吗 | ❌ 不能，子树在 BFS 序里不连续 |
直径、重心、路径¶
| 要点 | 结论 |
|---|---|
| 直径 | 树上最长简单路径；端点一定是叶子 |
| 两次 BFS | 任意点 → 最远点 \(a\) → 从 \(a\) 出发的最远点 \(b\) |
| ⚠️ 两次 BFS 的前提 | 边权非负；有负权必须树形 DP |
| 树形 DP 求直径 | 最长链 + 次长链；先更新答案再更新 down |
| 重心 | 删掉后最大块最小；等价于「距离和最小」；至多 2 个 |
| 重心的关键性质 | 最大子树 \(\le \lfloor n/2 \rfloor\) ⟹ 点分治深度 \(O(\log n)\) |
| 中心 | 到最远点最近；就是直径的中点。⚠️ 与重心不是一回事 |
| 路径边数 | \(\mathrm{dep}[u]+\mathrm{dep}[v]-2\mathrm{dep}[l]\) |
| 路径权和 | \(D[u]+D[v]-2D[l]\) |
| 路径异或和 | \(X[u]\oplus X[v]\)，不用减 |
| 判 \(w\) 在路径上 | \(\mathrm{dist}(u,w)+\mathrm{dist}(w,v)=\mathrm{dist}(u,v)\) |
| 树上点差分 | \(+k,+k\) 于 \(u,v\)；\(-k\) 于 \(l\)；\(-k\) 于 \(par(l)\) |
| 树上边差分 | \(+k,+k\) 于 \(u,v\)；\(\mathbf{-2k}\) 于 \(l\) |
LCA¶
| 要点 | 结论 |
|---|---|
| 倍增表 | \(fa_j[v]=fa_{j-1}[fa_{j-1}[v]]\)；整层列表推导建表 |
| 倍增查询 ① | 先把深的提到同层 |
| 倍增查询 ② | fa[j][x] != fa[j][y] 才跳（跳完仍不同才安全） |
⚠️ x == y |
必须在第二个循环前判，否则答案偏浅 |
| 0 号点哨兵 | fa[*][0] = 0，跳出树顶自动停住 |
| 欧拉序归约 | \(\mathrm{lca}(u,v)=\) 欧拉序 \([\mathrm{first}_u,\mathrm{first}_v]\) 里深度最小的点 |
| 编码技巧 | dep << 20 \| node，直接用内置 min 比较（要求 \(n<2^{20}\)） |
| ST 表建表 | list(map(min, prev, prev[h:])) —— 整层在 C 层 |
| \(n\) 大时的内存 | 朴素 ST 表 \(2\times10^7\) 元素必 MLE ⟹ 分块（\(B=64\)）+ 块间 ST 表 |
| Tarjan 离线 | 理论最优 \(O((n+q)\alpha)\)，但必须离线且 Python 常数不划算 |
| 只有倍增能做 | \(k\) 级祖先、路径最值（次小生成树用的就是它） |
| 选型 | \(q \le 10^5\) 或要跳 \(k\) 步 → 倍增；\(q \ge 3\times10^5\) → 欧拉序 + 分块 ST 表 |
| 规模 | Python 现实性 |
|---|---|
| 遍历 / BFS 序倒序，\(n \le 5\times10^5\) | ✅ 纯数组循环 |
| DFS 序 + 树状数组（子树改子树查），\(n \le 2\times10^5\) | ✅ |
| 直径（两次 BFS），\(n \le 5\times10^5\) | ✅ |
| 重心，\(n \le 5\times10^5\) | ✅ 一遍 sz + 一遍扫边 |
| LCA 倍增，\(n,q \le 2\times10^5\) | ⚠️ 约 3–4 s |
| LCA 倍增，\(n,q = 5\times10^5\) | ❌ \(2\times10^7\) 次 Python 层操作 |
| LCA 欧拉序 + 分块 ST 表，\(n,q = 5\times10^5\) | ⚠️ 8–15 s vs 6 s 时限，极险（BISHI124；PyPy 可过） |
| 树链剖分（线段树），\(n \le 10^5\) | ⚠️ 见 113 章 |
| 点分治，\(n \le 5\times10^4\) | ⚠️ \(O(n\log n)\) 但常数大 |
| 看到什么 → 想到什么 |
|---|
| 「\(n-1\) 条边 + 连通」 |
| 「输出先序/中序/后序」 |
| 「求子树的和 / 子树整体修改」 |
| 「先算儿子再算父亲」 |
| 「树上最长路径」 |
| 「删一个点使最大块最小」 |
| 「使到所有点距离和最小」 |
| 「使到最远点距离最小」 |
| 「多次询问两点距离 / 祖先」 |
| 「跳 \(k\) 级祖先 / 路径最大边」 |
| 「路径上所有点加 \(k\)，最后查每点」 |
| 「路径修改 + 路径查询」 |
| 「树上路径异或最大」 |