D. 树上倍增

很可惜这题被树剖暴力水过了。

20分搞法

直接暴力LCA。

40分搞法

老老实实写一个树上倍增或树链剖分。

100分搞法

这里有一个结论：多个节点的LCA，就是DFS序最大和最小的这两个节点的LCA。

我们尝试证明。DFS序是长成这样的：

要证明原命题，只需要证明这一种特化情况：

DFS序上，若有P < A < B，则有$\text {LCA} (P,A,B) = \text{LCA}(P,B)$。

由上图可以看出，我们把每个节点管理的区间画出来，不会交叉，只存在包含关系。

由于$\text {LCA} (P,A,B)$必定在$\text {LCA} (P,B)$到根节点的路径上，所以我们只需要证明：

DFS序上，若有P < A < B，则有$\text {LCA} (P,B)$是 $\text{LCA}(P,A)$的祖先。

这个证明就很简单了。不妨假设$\text{LCA}(P,A)$竟敢是$\text{LCA}(P,B)$的祖先，那么就会出现如下情况：

产生了交叉，所以这个假设不成立，原命题得证。

因此我们先把树的DFS序求出来，询问多个节点的LCA就变成了询问两个节点的LCA。

直接Tarjan就可以做了。