8551: BZOJ4551：[Tjoi2016&Heoi2016]树

在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下 两种操作：1. 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个 结点，可以打多次标记。）2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖 先）你能帮帮他吗?

输入格式

输入第一行两个正整数N和Q分别表示节点个数和操作次数接下来N-1行，每行两个正整数u,v(1≤u,v≤n)表示u到v 有一条有向边接下来Q行，形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询 问操作对于每次询问操作，1 ≤ N, Q ≤ 100000。

输出格式

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

样例输入

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

样例输出

1 
2 
2 
1

提示

 新加数据9组(By HFLSyzx ),未重测--2016.8.2

题目来源

没有写明来源