记录编号	389399	评测结果	AAAAAAAAAA
题目名称	[HNOI 2016] 网络	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	7.011 s
提交时间	2017-03-31 14:07:00	内存使用	35.41 MiB

//BZOJ 4538
//by Cydiater
//2017.3.31
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)	for(int i=j;i<=n;i++)
#define down(i,j,n)	for(int i=j;i>=n;i--)
#define cmax(a,b)	a=max(a,b)
#define cmin(a,b)	a=min(a,b)
#define Auto(i,node)	for(int i=LINK[node];i;i=e[i].next)
#define FILE		"network_tenderRun"

const int MAXN=2e5+5;
const int oo=0x3f3f3f3f;
const int LIM=1e9;

int N,M,ans[MAXN],cnt;

struct Query{
	int x,y,v,p,type;
}qry[MAXN],tmp[MAXN];

namespace BIT{
	int c[MAXN];
	inline int lowbit(int i){return i&(-i);}
	void add(int pos,int val){
		if(!pos)return;
		for(int i=pos;i<=N;i+=lowbit(i))c[i]+=val;
	}
	int get(int pos){
		int res=0;
		for(int i=pos;i>=1;i-=lowbit(i))res+=c[i];
		return res;
	}
	int Query(int L,int R){
		return get(R)-get(L-1);
	}
}

namespace Graph{
	struct edge{
		int y,next;
	}e[MAXN<<1];
	int LINK[MAXN],len=0,dep[MAXN],fa[MAXN][25],siz[MAXN];
	int dfsclock=0,dfn[MAXN],Pos[MAXN];
	inline void insert(int x,int y){
		e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;
	}
	inline void Insert(int x,int y){
		insert(x,y);
		insert(y,x);
	}
	void DFS(int node,int deep,int father){
		fa[node][0]=father;dep[node]=deep;
		siz[node]=1;dfn[++dfsclock]=node;
		Pos[node]=dfsclock;
		Auto(i,node)if(e[i].y!=father){
			DFS(e[i].y,deep+1,node);
			siz[node]+=siz[e[i].y];
		}
	}
	void GetAnc(){
		up(i,1,20)up(node,1,N)if(fa[node][i-1])
			fa[node][i]=fa[fa[node][i-1]][i-1];
	}
	int LCA(int x,int y){
		if(x==y)return x;
		if(dep[x]<dep[y])swap(x,y);
		down(i,20,0)if(dep[x]-(1<<i)>=dep[y])
			x=fa[x][i];
		if(x==y)return x;
		down(i,20,0)if(fa[x][i]&&fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
		return fa[x][0];
	}
}using namespace Graph;

namespace solution{
	void Work(int L,int R,int low,int hig){
		if(L==R||low==hig)return;
		int mid=(low+hig)>>1,j=L,k=R,num=0;
		up(i,L,R){
			if(qry[i].type!=2){
				if(qry[i].v<=mid)tmp[j++]=qry[i];
				else{
					int x=qry[i].x,y=qry[i].y,lca=LCA(x,y),flca=fa[lca][0],v=1;
					if(qry[i].type==1)v=-1;
					BIT::add(Pos[x],v);BIT::add(Pos[y],v);
					BIT::add(Pos[lca],-v);BIT::add(Pos[flca],-v);
					tmp[k--]=qry[i];
					num+=v;
				}
			}else{
				int x=qry[i].x;
				if(!num||BIT::Query(Pos[x],Pos[x]+siz[x]-1)==num)tmp[j++]=qry[i];
				else{
					cmax(ans[qry[i].p],mid+1);
					tmp[k--]=qry[i];
				}
			}
		}
		up(i,k+1,R)if(tmp[i].type!=2){
			int x=tmp[i].x,y=tmp[i].y,lca=LCA(x,y),flca=fa[lca][0],v=-1;
			if(tmp[i].type==1)v=1;
			BIT::add(Pos[x],v);BIT::add(Pos[y],v);
			BIT::add(Pos[lca],-v);BIT::add(Pos[flca],-v);
		}
		up(i,L,j-1)qry[i]=tmp[i];
		up(i,0,R-k-1)qry[i+k+1]=tmp[R-i];
		if(L<=j-1&&j-1<=R&&low<=mid)Work(L,j-1,low,mid);
		if(L<=k+1&&k+1<=R&&mid+1<=hig)Work(k+1,R,mid+1,hig);
	}
	void Prepare(){
		scanf("%d%d",&N,&M);
		up(i,2,N){
			int x,y;
			scanf("%d%d",&x,&y);
			Insert(x,y);
		}
		up(i,1,M){
			int t,x,y,v;
			scanf("%d",&t);
			if(t==0){
				scanf("%d%d%d",&x,&y,&v);
				qry[i]=(Query){x,y,v,0,0};
			}
			if(t==1){
				int p;
				scanf("%d",&p);
				int x=qry[p].x,y=qry[p].y,v=qry[p].v;
				qry[i]=(Query){x,y,v,0,1};
			}
			if(t==2){
				scanf("%d",&x);
				qry[i]=(Query){x,0,0,++cnt,2};
			}
		}
		memset(ans,-1,sizeof(ans));
		DFS(1,0,0);
		GetAnc();
	}
	void Solve(){
		Work(1,M,-1,LIM);
		up(i,1,cnt)printf("%d\n",ans[i]);
	}
}

int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	//freopen("input.in","r",stdin);
	using namespace solution;
	Prepare();
	Solve();
	return 0;
}