记录编号	287554	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tree—增强版	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	8.833 s
提交时间	2016-08-01 21:31:17	内存使用	58.26 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lch l,mid,rt<<1
#define rch mid+1,r,rt<<1|1
using namespace std;
const int maxn=1000010;
struct edge{
	int to;
	edge *prev;
	edge():to(0),prev(NULL){}
}ee[maxn<<1];
void insert(int,int);
void dfs1(int);
void dfs2(int,int);
int query(int);
int query(int,int,int,int,int);
void modify(int,int,int,int,int);
int len=0,tim=0;
int prt[maxn]={0},first[maxn]={0},finish[maxn]={0},top[maxn]={0},size[maxn]={0},son[maxn]={0},depth[maxn];
int a[maxn<<2]={0};
int n,x,y,m;
char c;
edge *last[maxn]={NULL};
int main(){
#define MINE
#ifdef MINE
	freopen("tree++.in","r",stdin);
	freopen("tree++.out","w",stdout);
#endif
	int __size__=64<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	scanf("%d%d",&n,&m);
	depth[0]=-0x80000000;
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		insert(x,y);
		insert(y,x);
	}
	depth[1]=1;
	dfs1(1);
	dfs2(1,1);
	modify(1,1,1,n,1);
	while(m--){
		scanf(" %c%d",&c,&x);
		if(c=='C')modify(first[x],x,1,n,1);
		else if(c=='Q')printf("%d\n",query(x));
	}
	return 0;
}
void insert(int x,int y){
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
void dfs1(int x){
	size[x]=1;
	for(edge *e=last[x];e;e=e->prev){
		if(e->to==prt[x])continue;
		prt[e->to]=x;
		depth[e->to]=depth[x]+1;
		dfs1(e->to);
		size[x]+=size[e->to];
		if(size[e->to]>size[son[x]])son[x]=e->to;
	}
}
void dfs2(int x,int tp){
	top[x]=tp;
	first[x]=++tim;
	if(son[x])dfs2(son[x],tp);
	for(edge *e=last[x];e;e=e->prev){
		if(e->to==prt[x]||e->to==son[x])continue;
		dfs2(e->to,e->to);
	}
	finish[x]=tim;
}
int query(int x){
	int ans=0,tmp;
	while(x){
		tmp=query(first[top[x]],first[x],1,n,1);
		if(depth[tmp]>depth[ans])ans=tmp;
		x=prt[top[x]];
	}
	return ans;
}
int query(int s,int t,int l,int r,int rt){
	if(s<=l&&t>=r)return a[rt];
	int mid=(l+r)>>1;
	if(t<=mid)return query(s,t,lch);
	if(s>mid)return query(s,t,rch);
	int x=query(s,t,lch),y=query(s,t,rch);
	if(depth[x]>depth[y])return x;
	else return y;
}
void modify(int p,int x,int l,int r,int rt){
	if(l==r){
		a[rt]=x;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid)modify(p,x,lch);
	else modify(p,x,rch);
	if(depth[a[rt<<1]]>depth[a[rt<<1|1]])a[rt]=a[rt<<1];
	else a[rt]=a[rt<<1|1];
}
/*
5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3
Answer:
1
2
2
1
*/