记录编号	495529	评测结果	AAAAAAAAAA
题目名称	2658.[SDOI 2017] 树点涂色	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	3.145 s
提交时间	2018-04-20 20:01:18	内存使用	15.89 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
#define ls x<<1
#define rs x<<1|1
using namespace std;
const int maxn=100010;
vector<int>p[maxn];
int n,m,cnt,ch[maxn][3];
int f[maxn],F[maxn],top[maxn],ed[maxn],siz[maxn],son[maxn],rnk[maxn],idx[maxn],dep[maxn];
int maxx[maxn*4],lazy[maxn*4];
void dfs1(int x){
	siz[x]=1;
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i];
		if(u==f[x])continue;
		f[u]=x,F[u]=x,dep[u]=dep[x]+1;
		dfs1(u),siz[x]+=siz[u];
		if(siz[u]>siz[son[x]])son[x]=u;
	}
}
void dfs2(int x,int y){
	top[x]=y,idx[x]=++cnt,rnk[cnt]=x;
	if(son[x])dfs2(son[x],y);
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i];
		if(u!=f[x]&&u!=son[x])dfs2(u,u);
	}
	ed[x]=cnt;
}
int lca(int x,int y){
	int f1=top[x],f2=top[y];
	while(f1!=f2){
		if(dep[f1]<dep[f2])swap(f1,f2),swap(x,y);
		x=f[f1],f1=top[x];
	}
	if(dep[x]>dep[y])swap(x,y);
	return x;
}
void downdata(int x){
	if(!lazy[x])return;
	maxx[ls]+=lazy[x],maxx[rs]+=lazy[x];
	lazy[ls]+=lazy[x],lazy[rs]+=lazy[x];
	lazy[x]=0;
}
void build(int x,int l,int r){
	if(l==r){maxx[x]=dep[rnk[l]];return;}
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	maxx[x]=max(maxx[ls],maxx[rs]);
}
void modify(int x,int l,int r,int L,int R,int d){
	if(L<=l&&r<=R){lazy[x]+=d,maxx[x]+=d;return;}
	downdata(x);
	int mid=(l+r)>>1;
	if(L<=mid)modify(ls,l,mid,L,R,d);
	if(R>=mid+1)modify(rs,mid+1,r,L,R,d);
	maxx[x]=max(maxx[ls],maxx[rs]);
}
int querymax(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R)return maxx[x];
	downdata(x);
	int res=0,mid=(l+r)>>1;
	if(L<=mid)res=max(res,querymax(ls,l,mid,L,R));
	if(R>=mid+1)res=max(res,querymax(rs,mid+1,r,L,R));
	return res;
}
bool get(int x){return rc(F[x])==x;}
bool isroot(int x){return lc(F[x])!=x&&rc(F[x])!=x;}
void rotate(int x){
	int fa=F[x],gf=F[fa],op=get(x),u=ch[x][op^1];
	if(!isroot(fa))ch[gf][rc(gf)==fa]=x;
	ch[fa][op]=u,ch[x][op^1]=fa;
	F[fa]=x,F[u]=fa,F[x]=gf;
}
void splay(int x){
	while(!isroot(x)){
		if(!isroot(F[x])){
			if(get(F[x])==get(x))rotate(F[x]);
			else rotate(x);
		}
		rotate(x);
	}
}
int findroot(int x){
	while(lc(x))x=lc(x);
	return x;
}
void access(int x){
	int u=0,root;
	while(x){
		splay(x);
		if(rc(x))root=findroot(rc(x)),modify(1,1,n,idx[root],ed[root],1);
		rc(x)=u;
		if(rc(x))root=findroot(rc(x)),modify(1,1,n,idx[root],ed[root],-1);
		u=x,x=F[x];
	}
}
int main(){
	freopen("paint.in","r",stdin);
	freopen("paint.out","w",stdout);
	scanf("%d%d",&n,&m);
	int u,v,op;
	for(int i=1;i<n;i++)scanf("%d%d",&u,&v),p[u].push_back(v),p[v].push_back(u);
	dep[1]=1,dfs1(1),dfs2(1,1);build(1,1,n);
	while(m--){
		scanf("%d%d",&op,&u);
		if(op==1)access(u);
		if(op==2){
			scanf("%d",&v);
			int ans=0,Lca=lca(u,v);
			ans=querymax(1,1,n,idx[u],idx[u])+querymax(1,1,n,idx[v],idx[v])-querymax(1,1,n,idx[Lca],idx[Lca])*2+1;
			printf("%d\n",ans);
		}
		if(op==3){
			int ans=querymax(1,1,n,idx[u],ed[u]);
			printf("%d\n",ans);
		}
	}
	return 0;
}