倍增法求LCA必须先统一深度再同步上跳：先让深节点跳至与浅节点同层，再二者同步上跳且绝不允许提前相会；否则可能访问未初始化的dep[0]导致错误。
倍增法求LCA：为什么必须先统一深度再同步上跳
树上倍增求lca不是“两个点一起往上蹦”，而是严格分两步：先让深的节点跳到和浅的同层，再一起往上跳但**绝不允许相会**。这一步逻辑错，结果就全错。
- 如果跳过“拉平深度”直接同步跳，
dep[x] 时x根本没资格参与第二步——它连第一层都还没站稳 - 第二步循环中用
if (f[x][i] != f[y][i])判断是否能跳，是为了停在LCA的**正下方一层**；一旦相等就跳出，最后返回f[x][0]才是答案 -
dep[0] = 0这个哨兵值必须设好，否则dep[f[x][i]] >= dep[y]可能访问非法内存（比如f[x][0]是0，而dep[0]未初始化）
dfs预处理中f[u][i]的递推顺序不能颠倒
倍增表f[u][i]表示u向上跳1步到达的祖先，它的计算依赖更小的步长——必须从i = 1开始递推，不能反着来。
- 错误写法：
for (int i = MAXK-1; i >= 1; i--) f[u][i] = f[f[u][i-1]][i-1];——此时f[u][i-1]可能还没算，结果是随机值 - 正确顺序：先确保
f[u][0]（父节点）已知，再从小到大循环i = 1 → MAXK-1，每次用已算好的f[u][i-1]更新f[u][i] - 常见坑：
MAXK取值要覆盖log2(n)，比如n ≤ 5e5就得至少20（因为2^19 ≈ 5.2e5），写19会漏掉最高位
Tarjan离线LCA：为什么必须标记“回溯完成”才合并进并查集
Tarjan本质是利用DFS时间戳和并查集维护“当前子树已访问部分的最近代表”，关键在于：只有当一个节点v彻底回溯完（即所有后代都处理完毕），才能把它和父节点u合并——否则会提前污染祖先路径。
- 标记数组
v[]三种状态：0=未访问，1=正在DFS栈中，2=已回溯完成；只有v[y] == 2时，才说明y所在子树已稳定，其并查集根才是可靠的LCA候选 - 如果在
dfs(y)刚进栈就f[y] = x，那么y的子树还没遍历，find(y)返回的可能是错误祖先 - 查询必须挂载在节点
x回溯前：遍历所有以x为一端的查询(x, y)，只对其中v[y] == 2的那些立即回答，其余留待后续
倍增 vs Tarjan：选哪个不看“快慢”，看“在线/离线”需求
倍增支持单次查询O(log n)，Tarjan批量处理m次查询均摊O(α(n))，但两者不可互换——核心差异在输入时机。
- 需要边读入边回答（比如交互题、流式数据），只能用倍增；Tarjan必须等全部查询收齐才能启动
- 倍增空间
O(n log n)，Tarjan仅O(n)；当n极大（如1e6）且内存紧张时，Tarjan更稳妥 - 倍增代码可复用于“查第k级祖先”“链上最大值”等扩展问题；Tarjan逻辑耦合强，改起来容易出错
真正卡住人的从来不是公式，而是dep[f[x][i]] >= dep[y]里那个等号要不要——少它，深度刚好对齐的节点就跳过了；多它，可能越界跳到0节点。这种边界得实测几个小样例才能放心。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
