倍增法求lca必须先建树并预处理深度和父节点，因为其本质是“跳表式向上查祖先”，需依赖depth[u]和upu（u的2^i级祖先）在o(log n)内完成深度对齐与同步上跳；若查询时临时dfs求深度，单次复杂度将退化为o(n)，彻底丧失倍增意义。
为什么倍增法求LCA必须先建树并预处理深度和父节点
因为倍增法本质是“跳表式向上查祖先”，不提前知道每个节点的深度和第 2^0、2^1、… 级祖先，就无法在 O(log n) 时间内对齐深度或同步上跳。常见错误是直接在查询时临时 DFS 求深度——这会让单次查询退化成 O(n)，完全失去倍增意义。
建树时建议用邻接表（vector<vector>></vector>），注意无向边要双向存；预处理用 BFS 或 DFS 均可，但 BFS 更自然（避免递归栈过深）。关键点是：根节点（如 1）的深度设为 0 或 1 要统一，后续所有跳转逻辑都依赖这个基准。
- 深度数组
depth[u]表示节点u到根的距离（边数） - 倍增表
up[u][i]表示u的第2^i级祖先，其中i范围是0到LOGN（通常取20足够覆盖1e6节点） -
up[u][0]就是直接父节点，由建树过程确定；其余靠递推：up[u][i] = up[up[u][i-1]][i-1]
怎么写 LCA 查询函数：先对齐深度再同步上跳
查询 lca(u, v) 两步不能颠倒：必须先让深的节点跳到和浅的同一深度，否则同步跳会错位。常见错误是忽略深度相等时直接返回，或在对齐后没检查是否已是同一节点。
对齐深度用的是二进制拆分思想：从大到小枚举 i（LOGN 到 0），只要 depth[u] - (1 = depth[v]，就让 u = up[u][i]。同步上跳同理：从大到小枚举 i，若 up[u][i] != up[v][i]，则同时跳，最后返回 up[u][0]（即最近公共父节点）。
- 务必在对齐后加
if (u == v) return u;，否则可能多跳一级 - 循环中判断条件用
!=而非==，是因为我们要停在“刚好不同”的那一层，再跳一级才是答案 - 所有
i枚举必须从大到小，否则无法保证跳得“贪心且不越界”
倍增数组大小怎么设才不越界又省空间
二维数组 up[MAXN][LOGN] 的第二维不能只开 20 就完事——如果树退化成链，最大深度接近 MAXN，那么需要的 i 上限是 floor(log2(MAXN)) + 1。例如 MAXN = 500000，log2(500000) ≈ 19.9，所以 LOGN 至少取 20；保险起见常设为 21 或 22。
第一维大小必须 ≥ 节点总数，且下标从 1 开始（如果输入节点编号从 1）。容易被忽略的是：初始化时 up[u][0] 必须显式赋值（比如根节点设为 0 或自身），其余 i > 0 的项可用循环递推，但别忘了对根节点的 up[root][i] 统一设为 0 或 -1（表示无效），否则未初始化内存可能造成随机跳转。
- 推荐用
memset(up, -1, sizeof up)初始化，然后对有效边单独赋值up[u][0] - 若用
vector<vector>></vector>动态开，第二维大小固定为LOGN，比静态数组更安全 - 空间复杂度是
O(n log n)，当n = 1e6、LOGN = 20时约需 160MB，竞赛中需留意内存限制
调试时遇到 “RE” 或 “WA” 最可能卡在哪几个地方
倍增 LCA 的典型崩溃点不在算法逻辑本身，而在边界与索引。最常触发段错误（RE）的是访问了 up[u][i] 中无效的 u 或越界的 i；WA 则多因深度对齐不彻底或同步跳时没跳到最后一层。
- 检查输入节点编号是否真在
[1, n]范围内，特别是有多组数据时忘记重置depth数组 - BFS/DFS 预处理时，是否给每个节点都设置了
depth[u]和up[u][0]？漏掉某个叶子会导致其up[u][0]是垃圾值 - 查询前没确保
u和v是已建树中的合法节点（比如读入错误、离线查询时映射错） - 使用
up[u][i]前没判up[u][i] != -1（如果用 -1 表示无效），尤其在对齐深度循环里
真正难调的不是主逻辑，而是那个没初始化的 up[1][5]——它可能恰好等于某个真实节点编号，导致祖先关系错乱，这种 bug 很难靠打印发现。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
