#P3077. [HEOI2016/TJOI2016] 树

[HEOI2016/TJOI2016] 树

题目描述

在 2016 年,佳媛姐姐刚刚学习了树,非常开心。现在他想解决这样一个问题:给定一颗有根树,根为 11 ,有以下两种操作:

  1. 标记操作:对某个结点打上标记。(在最开始,只有结点 11 有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)

  2. 询问操作:询问某个结点最近的一个打了标记的祖先。(这个结点本身也算自己的祖先)

你能帮帮她吗?

输入格式

第一行两个正整数 NNQQ 分别表示节点个数和操作次数。

接下来 N1N-1 行,每行两个正整数 u,v(1u,vn)u,v \,\, (1 \leqslant u,v \leqslant n) 表示 uuvv 有一条有向边。

接下来 QQ 行,形如 oper numoperC 时表示这是一个标记操作, operQ 时表示这是一个询问操作。

输出格式

输出一个正整数,表示结果

5 5 
1 2 
1 3 
2 4 
2 5 
Q 2 
C 2 
Q 2 
Q 5 
Q 3
1
2
2
1

提示

30%30\% 的数据,1N,Q10001 \leqslant N, Q \leqslant 1000

70%70\% 的数据,1N,Q100001 \leqslant N, Q \leqslant 10000

100%100\% 的数据,1N,Q1000001 \leqslant N, Q \leqslant 100000