提高组知识2——LCA

[王皓宇 (小鸽子)]

依旧一个非常小笨蛋的做法

n² 预处理 i 是否处于 j 的子树

LCA只有一个点，这个点的所有祖先也是这两个节点的祖先（注意不一定是最近的）

对于每次查询，O(n)遍历一下所有点，找到深度最深的点z的使x和y都处于自己的子树

时间复杂度O（n² + nm）

这样要5e11，CCF的评测机是绝对过不了的

当然这是可以优化的

再预处理一下节点深度

把节点放入对应深度的集合里

这样找节点时只需要找大于等于a和b中深度最大的深度集合进行遍历

也可以直接从根节点dfs，由于LCA的祖先也是ab的祖先，因此每次只会递归一次，当无法递归时，该节点就是a和b的LCA

---

回归正题

既然是总结帖，那肯定是写正解了

我们可以知道，深度大的节点一定不可能是LCA（祖先的深度不能比儿子大吧？）

那么我们可以把两个节点深度统一为小的那一个（如下图）

此时只需将两个点同时变为自己的父亲（向上）

直至两个点相同

时间复杂度O（N）

最后时间复杂度O（NM）

（实际上根本没有区别吧）

的确死了，还挺惨

接下来要进行优化

这里建议去看一下倍增

好了，那么接下来讲优化

对于一个形如下图的树

此时求LCA的速度肯定慢

因为它在一步步向上转移的过程中并没有计算出结果

我们肯定希望中间的转移过程尽量简单

这就验证了上文

我们只要找到离我们最近的 “ 1 ”（指祖先相同的最大深度，想歪的自觉罚站）

或离我们最远的 “ 0 ”，（它的父亲节点就是 离我们最近的 “ 1 ” ）

预处理每个节点向上 2 ^ k 的祖先

将 f_{i,k} 表示 节点 i 向上 2 ^ k 的祖先

转移就是 f_{i,k} = f_{f_{i,k-1},k-1}

k = 0 的情况在dfs的过程中直接处理（就是父节点）

如果 f_{a,k} 不等于 f_{b,k}

就 a = f_{a,k} , b = f_{b,k}

这样我们就找到了 离我们最远的 “ 0 ”

此时 f_{a,0} = f_{b,0} , 就是 a 和 b 的LCA

比较抽象，看一下代码

好了，下课！！！

[江亚君]

挺好的

[许可越 (yhcorey)]

谁告诉你跑不了 5\times10^{11} 的？

怎么Big_J还在啊

[王皓宇 (小鸽子)]

今年CCF的评测机的确过不了吧

[王皓宇 (小鸽子)]

1s跑 5\times 10^{11} 只是理想状态，实际是比较难做到的吧

[许可越 (yhcorey)]

神威·太湖之光

[王皓宇 (小鸽子)]

额……CCF很有钱了

[许可越 (yhcorey)]

怎么可能没钱

[王皓宇 (小鸽子)]

这里是总结帖，请问一些有价值的问题或讨论，不要发这种无关紧要的帖子