@ruanxingzhi
2017-10-22T23:40:05.000000Z
字数 454
阅读 2229
现有一棵树。您需要写一个树上倍增算法,以实现如下操作:
A x
新建一个节点,将它作为x
节点的儿子,编号为当前节点总数+1
。Q k p1 p2 p3....
查询p1,p2,p3...
这些节点的LCA。其中k
表示查询节点的个数。最初树上只有一个节点,编号为1
。
多个节点的LCA定义为:这些节点的公共祖先中深度最大的。
第一行,一个正整数,表示操作个数。
接下来行,每行输入一个操作,格式如题目描述
所述。
保证任何输入的数都是正整数。
对于每一个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
。
对于的数据,有。
对于的数据,有。
对于的数据,有。
保证询问不超过次。