记录编号	397615	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]榴莲	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	2.479 s
提交时间	2017-04-20 19:33:24	内存使用	17.80 MiB

#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#define N 100010
#define l(x) x<<1
#define r(x) (x<<1)|1
#define INF 0x7f7f7f7f
typedef long long LL;
using namespace std;

int n,m,i,x,y,tot,lsum=1,L=1;
int q[N],ans[N];
int tmp[2][N];
int ss[N],s[N],hson[N],fa[N],top[N],Right[N],v[N],h[N],Rank[N],w[N],head[N],Head[N];

struct Edge{
	int t,next;
}E[N*2],son[N*2];

inline void Add(int s,int t){E[lsum].t=t;	E[lsum].next=head[s];	head[s]=lsum++;}

inline void ADD(int s,int t){son[L].t=t;	son[L].next=Head[s];	Head[s]=L++;}

struct Date{
	int sign,s,x,y;
}a[N],b[N];

inline void Swap(int &x,int &y){x^=y^=x^=y;}

namespace IO{
	char buf[1<<15],*fs,*ft;
	inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int gint(){
		int x=0,ch=gc();
		while(ch<'0'||ch>'9') ch=gc();
		while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=gc();
		return x;
	}
}
using namespace IO;

struct SegMentTree{
	int d[4*N];	short z[4*N];
	inline void Add(int x,int low,int &high,int val,int l,int r){
		int mid=(l+r)>>1;
		if (low>high)	return;
		if (l==low&&r==high) {
			d[x]+=val*(r-l+1);	z[x]+=val;	return;
		}
		if (high<=mid)	Add(l(x),low,high,val,l,mid);	else
		if (low>mid)	Add(r(x),low,high,val,mid+1,r);	else
		Add(l(x),low,mid,val,l,mid),Add(r(x),mid+1,high,val,mid+1,r);
		d[x]=d[l(x)]+d[r(x)];
	}
	
	inline int Query(int x,int &low,int l,int r){
		int mid=(l+r)>>1;
		if (l==r)	return d[x];
		if (low<=mid)	return Query(l(x),low,l,mid)+z[x];
		else return Query(r(x),low,mid+1,r)+z[x];
	}
}SMT;

inline void Maketree(int &x){
	int i=0,t=0;
	v[x]=1;	s[x]++;
	for (i=head[x];i;i=E[i].next)
	if (!v[E[i].t]){
		t=E[i].t;	h[t]=h[x]+1;	fa[t]=x;
		ADD(x,t);
		//son[x].push_back(t);
		Maketree(t);	s[x]+=s[t];
		(s[t]>ss[x])?ss[x]=s[t],hson[x]=t:0;
	}
}

inline void Cut(int &x){
	int i=0,t=0;
	w[x]=++tot;	Rank[tot]=x;
	if (!hson[x])	{Right[x]=tot;	return;}
	top[hson[x]]=top[x];	Cut(hson[x]);
	for (i=Head[x];i;i=son[i].next){
		t=son[i].t;
		if (t==hson[x])	continue;
		top[t]=t;	Cut(t);
	}
	Right[x]=tot;
}

inline int Get_LCA(int x,int y){
	int f1=top[x],f2=top[y];
	for (;f1!=f2;){
		(h[f1]<h[f2])?Swap(x,y),Swap(f1,f2):(void)0;
		f1=top[x=fa[f1]];
	}
	(h[x]>h[y])?Swap(x,y):(void)0;
	return x;
}

inline void Add(int &x,int &y,int V){
	int LCA=Get_LCA(x,y),i=x;
	for (;h[top[i]]>h[LCA];){
		SMT.Add(1,w[top[i]],w[i],V,1,n);	i=fa[top[i]];
	}
	SMT.Add(1,w[LCA],w[i],V,1,n);	i=y;
	for (;h[top[i]]>h[LCA];){
		SMT.Add(1,w[top[i]],w[i],V,1,n);	i=fa[top[i]];
	}
	SMT.Add(1,w[LCA]+1,w[i],V,1,n);
}

inline void Solve(int L,int R,int l,int r){
	int i=0,t1=0,t2=0,T=0,cnt=0,mid=(l+r)>>1,L1=0,L2=0;
	if (L>R)	return;
	if (l==r){
		for (i=L;i<=R;ans[q[i]]=l,i++);
		return;
	}
	L1=L2=0;
	for (i=L;i<=R;i++){
		T=q[i];
		if (a[T].sign==1){
			if (a[T].s<=mid)	tmp[0][++L1]=T;
			else {
				tmp[1][++L2]=T;	Add(a[T].x,a[T].y,1);
			}
		}	else
		if (a[T].sign==2){
			if (a[T].s<=mid)	tmp[0][++L1]=T;
			else {
				tmp[1][++L2]=T;	SMT.Add(1,w[a[T].x],Right[a[T].x],1,1,n);
			}
		}	else
		if (a[T].sign==3){
			if (b[T].s<=mid)	tmp[0][++L1]=T;
			else {
				tmp[1][++L2]=T;
				(b[T].sign==1)?Add(b[T].x,b[T].y,-1):SMT.Add(1,w[b[T].x],Right[b[T].x],-1,1,n);
			}
		}	else{
			cnt=SMT.Query(1,w[a[T].x],1,n);
			if (cnt<a[T].s){
				a[T].s-=cnt;	tmp[0][++L1]=T;
			}	else tmp[1][++L2]=T;
		}
	}
	for (i=L;i<=R;i++){
		T=q[i];
		if (a[T].sign==1&&a[T].s>mid)	Add(a[T].x,a[T].y,-1);	else
		if (a[T].sign==2&&a[T].s>mid)	SMT.Add(1,w[a[T].x],Right[a[T].x],-1,1,n);	else
		if (a[T].sign==3&&b[T].s>mid)
			(b[T].sign==1)?Add(b[T].x,b[T].y,1):SMT.Add(1,w[b[T].x],Right[b[T].x],1,1,n);
	}
	t1=L;	t2=L+L1-1;
	for (i=1;i<=L1;q[t1++]=tmp[0][i],i++);
	for (i=1;i<=L2;q[t1++]=tmp[1][i],i++);
	Solve(L,t2,l,mid);	Solve(t2+1,R,mid+1,r);
}

inline int Main(){
	freopen("Durio_zibethinus_Murr.in","r",stdin);
	freopen("Durio_zibethinus_Murr.out","w",stdout);
	n=gint();	m=gint();
	for (i=1;i<n;i++){
		x=gint();	y=gint();	Add(x,y);	Add(y,x);
	}
	x=1;	Maketree(x);	top[1]=1;	Cut(x);
	for (i=1;i<=m;i++){
		a[i].sign=gint();
		switch (a[i].sign){
			case 1:{a[i].x=gint();	a[i].y=gint();	a[i].s=gint();	break;}
			case 2:{a[i].x=gint();	a[i].s=gint();	break;}
			case 3:{a[i].s=gint();	b[i]=a[a[i].s];	break;}
			case 4:{a[i].x=gint();	a[i].s=gint();	break;}
		}
		q[i]=i;
	}
	Solve(1,m,0,100010);
	for (i=1;i<=m;i++)
	if (a[i].sign==4)	if (ans[i])	printf("%d\n",ans[i]);	else puts("-1");
	fclose(stdin);	fclose(stdout);
	return 1;
}
int M=Main();
int main(){
}