#2486. 「CEOI2011」Treasure Hunt

内存限制:256 MiB 时间限制:4000 ms 题目类型:交互
上传者: diamond_duke

题目描述

现在有一棵树,初始时只有一个根节点 1 ,你需要完成下列两种操作:

  • path u s 表示在 u 下面依次加入了 s 个节点:其中的第 i 个节点作为第 i-1 个节点的孩子( 2\le i\le s ),特别地,第 1 个节点会作为 u 的孩子。设加入前时,树中节点的最大编号为 n ,则新加入的 s 个点会被依次编号为 n+1,n+2,\cdots,n+s
  • dig u v 表示询问 u,v 的中点。形式化地,设 u,v 间的距离为 d ,则你需要求出 u,v 的路径上,距离 u \lfloor \frac d2\rfloor 的节点编号。

输入格式

本题是一道交互题,首先你需要从标准输入读入操作次数 n
接下来 n 次,你会得到以下两种格式的指令之一:

  • P u s 表示一次 path u s 的操作;
  • D u v 表示一次 dig u v 的操作。

对于第一种操作,你不需要输出任何东西。对于第二种操作,你必须给出答案并清空缓冲区后(C/C++中的fflush(stdout)),才可以读取后续操作。

输出格式

对于每一次 D u v 的操作,输出一行表示答案,保证至少有一次这样的操作。

样例

样例输入

12
P 1 2
D 1 3
P 2 5
D 7 3
D 3 7
P 1 2
P 3 3
D 10 11
P 5 1
D 14 8
D 2 4

样例输出

2
5
4
1
6
2

数据范围与提示

对于 20\% 的数据,保证最终点的编号最大不超过 5000 ,且 n\le 5000
对于 50\% 的数据,保证最终点的编号最大不超过 400\ 000
对于 100\% 的数据,保证最终点的编号最大不超过 10^9 ,且 n\le 400\ 000