F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5165. -- 树上倍增

5165: 树上倍增

Time Limit: 25 Sec  Memory Limit: 256 MB
Submit: 380  Solved: 124
[Submit][Status][Discuss]

Description

现有一棵树。您需要写一个树上倍增算法,以实现如下操作:
A x 新建一个节点,将它作为x节点的儿子,编号为当前节点总数+1。
Q k p1 p2 p3.... 查询p1,p2,p3...这些节点的LCA。其中k表示查询节点的个数。
最初树上只有一个节点,编号为1。 
多个节点的LCA定义为:这些节点的公共祖先中深度最大的。

Input

第一行,一个正整数,表示操作个数。 
接下来行,每行输入一个操作,格式如题目描述所述。
保证任何输入的数都是正整数。
n≤3000000 k≤1000。
保证询问不超过1000次

Output

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

Sample Input

10
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

Sample Output

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

HINT

Source

ruanxingzhi版权所有

[Submit][Status][Discuss]

HOME Back