×

计蒜客

  1. 题库
  2. 一道简单题
  3. 问答
  • 8.14%
  • 65536K

题目描述

给出一棵二叉树,现有以下两种操作:

1. Q u:查询操作,查询u节点最左后代节点编号。如果没有左儿子,则输出自身。

2. C u:修改操作,左右翻转子树u。

输入格式

第一行输入正整数 T(T <= 30),表示共有T组输入数据。

对于每组数据,第一行输入两个正整数n,q(n <= 100000,q <= 100000),表示一棵 n 个节点的二叉树,节点编号1 到 n,有 q 次操作。

接下来 2 到 n 行,其中第 i 行输入两个正整数 t,p。t = 0 表示 i 是 p 的左儿子,t = 1 表示 i 节点是 p 节点的右儿子。接下来 n + 1 到 n + m 行,代表 m 次操作。格式如上所述。

输出格式

对于每个查询操作,输出相应的结果。

样例输入

2
3 3
0 1
1 1
Q 1
C 1
Q 1
3 3
0 1
0 2
Q 1
C 2
Q 2

样例输出

2
3
3
2

题目来源

北方大学 ACM 多校训练赛 第十四场

想挑战这道题吗

  • main.c