记录编号	365012	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 树	最终得分	100
用户昵称	核糖核酸	是否通过	通过
代码语言	C++	运行时间	0.288 s
提交时间	2017-01-19 07:36:53	内存使用	4.87 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
#define L(a) (a<<1)
#define R(a) (a<<1|1)
using namespace std;
static int n, m, x, Index;
static int dfn1[N], dfn2[N], dep[N];
static int head[N], nex[N*2], to[N*2], cnt;
char opt[3];

void Link(int x, int y) {
	nex[++cnt] = head[x]; head[x] = cnt;
	to[cnt] = y;
}

void dfs(int p, int f) {
	dep[p] = dep[f] + 1;
	dfn1[p] = ++Index;
	for(int j=head[p]; j; j=nex[j])
		if(to[j] != f) dfs(to[j], p);
	dfn2[p] = Index;
}

int fa[N*4];

void Build(int p, int l, int r) {
	fa[p] = 1;
	if(l == r) return;
	int mid = (l + r) >> 1;
	Build(L(p), l, mid); Build(R(p), mid+1, r);
}

void Modify(int p, int Le, int Re, int l, int r, int x, int f) {
	if(dep[f] >= dep[fa[p]]) fa[p] = f;
	if(Le == l && Re == r) {
		if(dep[x] >= dep[fa[p]]) fa[p] = x;
		return;
	}
	int mid = (Le + Re) >> 1;
	if(r <= mid) Modify(L(p), Le, mid, l, r, x, fa[p]);
	else if(l > mid) Modify(R(p), mid+1, Re, l, r, x, fa[p]);
	else {
		Modify(L(p), Le, mid, l, mid, x, fa[p]);
		Modify(R(p), mid+1, Re, mid+1, r, x, fa[p]);
	}
}

int  Query(int p, int l, int r, int x, int f) {
	if(dep[f] >= dep[fa[p]]) fa[p] = f;
	if(l == r) return fa[p];
	int mid = (l + r) >> 1;
	if(x <= mid) return Query(L(p), l, mid, x, fa[p]);
	else return Query(R(p), mid+1, r, x, fa[p]);
}

int main() {
	freopen("heoi2016_tree.in", "r", stdin);
	freopen("heoi2016_tree.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	for(int i=1; i<n; i++) {
		int u,v; scanf("%d%d", &u, &v);
		Link(u, v); Link(v, u);
	}
	dfs(1, 0);
	Build(1, 1, n);
	while(m--) {
		scanf("%s%d", opt, &x);
		if(opt[0] == 'C')
			Modify(1, 1, n, dfn1[x], dfn2[x], x, 1);
		else printf("%d\n", Query(1, 1, n, dfn1[x], 1));
	}
	
	return 0;
}