2304. [HZOI 2015]简单的最近公共祖先

题目描述：

给定一棵有根树，树根为1

一开始树上所有节点都是白色的，要求你维护以下操作：

1、C 将树上所有黑色节点变成白色

2、M u 将u节点染黑

3、Q u 查询u和所有黑色节点的所有LCA的深度最大的点的编号

LCA定义为两个点的最近公共祖先

输入格式：

第一行输入n，m表示节点总数和操作总数

以下n-1行每行u，v描述树上的一条边的两个端点

以下m行每行描述一个询问如题所示

n,m<=2000000

输出格式：

对于每个Q询问输出相应的答案

如果没有LCA的话输出-1

输入样例：

10 10

1 2

1 3

2 4

3 5

4 6

3 7

4 8

7 9

8 10

M 9

M 9

M 6

Q 10

Q 5

M 9

C

Q 6

M 4

M 5

输出样例：

4

3

-1

提示：

注意输入数据较大，推荐使用读入优化

由于cojs评测机的问题，可能会爆栈，所以请在main函数的开头加入如下程序：

int __size__=128<<20;

char *__p__=(char*)malloc(__size__)+__size__;

__asm__("movl %0, %%esp\n"::"r"(__p__));

注意上述代码会占用你128MB的空间，请自行修改，测试数据大约开到70MB就可以了

本题开了标程两倍的时限，而且是黑白树系列的某道题的加强版，原做法是难以通过的

本题的做法是本人自己想出来的，如果有更好的做法，欢迎与我联系

本来想强制在线的，但是为了更好的算法的出现就没有强制 强制在线