[Tjoi2016&Heoi2016]树
时间限制：20s 空间限制：128MB
题目描述
在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
题目来源
没有写明来源