题目描述

现有一棵树。您需要写一个树上倍增算法，以实现如下操作：

• A x 新建一个节点，将它作为x节点的儿子，编号为当前节点总数+1。
• Q k p1 p2 p3.... 查询p1,p2,p3...这些节点的LCA。其中k表示查询节点的个数。

最初树上只有一个节点，编号为1。
多个节点的LCA定义为：这些节点的公共祖先中深度最大的。

输入格式

第一行，一个正整数$n$，表示操作个数。
接下来$n$行，每行输入一个操作，格式如题目描述所述。

保证任何输入的数都是正整数。

输出格式

对于每一个Q操作，输出一行一个正整数，表示所询问节点的LCA。

样例数据

样例输入

7
A 1
A 2
A 3
A 1
A 5
A 5
Q 2 3 6
Q 2 6 7
Q 2 4 2
Q 3 7 6 5

样例输出

1
5
2
5

解释

3,6的LCA是1。
6,7的LCA是5。
4,2的LCA是2。
7,6,5的LCA是5。

数据规模与约定

对于$20\%$的数据，有$n \leq 100,k=2$。
对于$40\%$的数据，有$n \leq 100000,k\leq 10$。
对于$100\%$的数据，有$n \leq 1000000,k\leq 1000$。
保证询问不超过$1000$次。

题解

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

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就可以做了。

转自阮行止

下面是我的证明：

因为最后的答案肯定是这些节点中任意两个节点的公共祖先，所以，最后的答案肯定是DFS序最大和最小的这两个节点的LCA的祖先（包括自身）。我们只需要再证明这个节点是其它所以节点的祖先即可。我们考虑DFS序，以一个节点为根的子树的所有节点的DFS序是连续的一段区间，该节点既然已经是DFS序最大和最小的这两个节点的祖先了，那么DFS序在这两个点之间的节点肯定是该节点的后代，所以命题得证。