故事族谱查询与巡线打卡
你在一家做家族谱系的产品公司实习。族谱是一棵 50 万个节点的树（祖先在上、后代在下）。用户每天要问 50 万次这样的问题：
问题一：「我和我表弟最近的共同祖先是谁？」（这就是 LCA，最近公共祖先）
问题二：「我们俩之间的血缘距离是多少？」
如果你每次都从两个人往上爬到根再比对，深度最坏 50 万，单次查询就 50 万次操作，50 万次查询就是 2500 亿次——服务器直接冒烟。
更麻烦的是任务三：运维要在族谱上「巡线打卡」。给你 50 万条路径（每条路径从一个族人走到另一个族人），要求最后统计出每个族人一共被多少条路径经过。一条一条路径地去加，同样会跑爆。
两个看似不同的问题，其实只要两个武器。
• 倍增：把「向上跳 k 步」用二进制拆开，预处理 fa[u][j] 表示「u 往上跳 2^j 步到达的点」。于是任何一次向上跳都是 O(log n)，求 LCA 也只需要 O(log n)。
• 树上差分：把「路径整体加 1」翻译成「在四个点上打标记」。所有路径都打完标记后，做一次 DFS 回溯把子树标记累加到父亲上，就能得到每个点的真实覆盖次数。
倍增负责「快速定位」，差分负责「批量修改」，两者结合就是树上路径问题的万能钥匙。
💡 为什么这两个技术必须放在一起学？
因为树上差分需要用 LCA。无论是点差分还是边差分，公式里都会出现 lca(u,v) 和 fa[lca(u,v)]。所以你必须先有 O(log n) 的 LCA，才能在 O(1) 时间内完成一条路径的差分标记。
整体复杂度：预处理 O(n log n) + 每次路径操作 O(log n) + 最后一次性 DFS 结算 O(n)。相比暴力枚举路径的 O(n·m)，这是数量级的飞跃。