[HEOI2016/TJOI2016] 树
题目描述
在 2016 年,佳媛姐姐刚刚学习了树,非常开心。现在他想解决这样一个问题:给定一颗有根树,根为 $1$ ,有以下两种操作:
1. 标记操作:对某个结点打上标记。(在最开始,只有结点 $1$ 有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)
2. 询问操作:询问某个结点最近的一个打了标记的祖先。(这个结点本身也算自己的祖先)
你能帮帮她吗?
输入输出格式
输入格式
第一行两个正整数 $N$ 和 $Q$ 分别表示节点个数和操作次数。
接下来 $N-1$ 行,每行两个正整数 $u,v \,\, (1 \leqslant u,v \leqslant n)$ 表示 $u$ 到 $v$ 有一条有向边。
接下来 $Q$ 行,形如 `oper num` ,`oper` 为 `C` 时表示这是一个标记操作, `oper` 为 `Q` 时表示这是一个询问操作。
输出格式
输出一个正整数,表示结果
输入输出样例
输入样例 #1
5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3
输出样例 #1
1
2
2
1
说明
$30\%$ 的数据,$1 \leqslant N, Q \leqslant 1000$ ;
$70\%$ 的数据,$1 \leqslant N, Q \leqslant 10000$ ;
$100\%$ 的数据,$1 \leqslant N, Q \leqslant 100000$ 。