@ruanxingzhi
2017-05-06T23:26:06.000000Z
字数 471
阅读 1503
很可惜这题被树剖暴力水过了。
直接暴力LCA。
老老实实写一个树上倍增或树链剖分。
这里有一个结论:多个节点的LCA,就是DFS序最大和最小的这两个节点的LCA。
我们尝试证明。DFS序是长成这样的:
要证明原命题,只需要证明这一种特化情况:
DFS序上,若有
P < A < B
,则有。
由上图可以看出,我们把每个节点管理的区间画出来,不会交叉,只存在包含关系。
由于必定在到根节点的路径上,所以我们只需要证明:
DFS序上,若有
P < A < B
,则有是 的祖先。
这个证明就很简单了。不妨假设竟敢是的祖先,那么就会出现如下情况:
产生了交叉,所以这个假设不成立,原命题得证。
因此我们先把树的DFS序求出来,询问多个节点的LCA就变成了询问两个节点的LCA。
直接Tarjan就可以做了。