记录编号	276310	评测结果	EEEEEEEEEE
题目名称	[HZOI 2015]简单的最近公共祖先	最终得分	0
用户昵称	prefect1999	是否通过	未通过
代码语言	C++	运行时间	1.444 s
提交时间	2016-07-03 19:03:05	内存使用	144.46 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <ctype.h>
#define lowbit(x) ((x)&(-x))
const int maxn = 2100000;
int depth[maxn], color[maxn], time[maxn], counter = 1;
inline int ReadInt()
{
    char ch = getchar();
    int data = 0;
    while (ch < '0' || ch > '9')
        ch = getchar();
    do
    {
        data = data*10 + ch-'0';
        ch = getchar();
    } while (ch >= '0' && ch <= '9');
    return data;
}
struct edge
{
	int from, to, cost;
};
edge e[maxn];
int dep[maxn], size[maxn], pa[maxn], id[maxn], son[maxn], val[maxn], top[maxn], rev[maxn];
int head[maxn*2], data[maxn*2], next[maxn*2], sz = 1; //!!!!!!!!!!!
int n, m, num;
void Insert(int x, int y)
{
	next[sz] = head[x];
	head[x] = sz;
	data[sz] = y;
	++sz;
}
void dfs1(int u, int fa, int d)
{
	dep[u] = d;
	size[u] = 1;
	son[u] = 0;
	pa[u] = fa;
	for (int i = head[u]; i != 0; i = next[i])
	{
		int v = data[i];
		if (v != fa)
		{
			dfs1(v, u, d + 1);
			size[u] += size[v];
			if (size[son[u]] < size[v])
				son[u] = v;
		}
	}
}
void dfs2(int u, int tp)
{
	top[u] = tp;
	id[u] = ++num;
	rev[num] = u;
	if (son[u])
		dfs2(son[u], tp);
	for (int i = head[u]; i != 0; i = next[i])
	{
		int v = data[i];
		if (v != pa[u] && v != son[u])
			dfs2(v, v);
	}
}
void Prepare()
{
	for (int i = 1; i < n; ++i)
	{
		e[i].from = ReadInt();
		e[i].to = ReadInt();
		Insert(e[i].from, e[i].to);
		Insert(e[i].to, e[i].from);
	}
	num = size[0] = 0;
	dfs1(1, 0, 1);
	dfs2(1, 1);
}
int Update(int u)
{
	int x = top[u];
	while (u != 0)
	{
		if (time[x] != counter)
			time[x] = counter, depth[x] = 0;
		depth[x] = std::max(depth[x], dep[u]);
		u = pa[x];
		x = top[u];
	}
	return -1;
}
int Ask(int u)
{
	int x = top[u];
	while (u != 0)
	{
		if (time[x] != counter)
			time[x] = counter, depth[x] = 0;
		if (depth[x] > 0)
		{
			int d = std::min(dep[u], depth[x]) - dep[x];
			return rev[id[x]+d];
		}
		u = pa[x];
		x = top[u];
	}
	return -1;
}
int main()
{
	int __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	freopen("get_tree.in", "r", stdin);
	freopen("get_tree.out", "w", stdout);
	n = ReadInt(); m = ReadInt();
	Prepare();
	for (int i = 0; i < m; ++i)
	{
		char tp;
		int u;
		while (!isalpha(tp = getchar()));
		if (tp == 'C')
		{
			++counter;
		}
		else if (tp == 'M')
		{
			u = ReadInt();
			if (color[u] != counter)
			{
				Update(u);
				color[u] = counter;
			}
		}
		else
		{
			u = ReadInt();
			printf("%d\n", Ask(u));
		}
	}
	return 0;
}