记录编号	346693	评测结果	AAAAAAAAAA
题目名称	[HNOI 2016] 网络	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	25.508 s
提交时间	2016-11-12 14:26:44	内存使用	26.91 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=500010;
struct edge{int f,t;}w[N];
int n,m,fa[N],head[N],tail[N],next[N];
void add(int f,int num){
	if (!head[f]) head[f]=tail[f]=num;
		else tail[f]=next[tail[f]]=num;
}
//树剖 
int size[N],dfn[N],h[N],cnt,hash[N],big[N],link[N];
void dfs(int x){
	size[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i].t]){
		fa[w[i].t]=x;
		h[w[i].t]=h[x]+1;
		dfs(w[i].t);
		size[x]+=size[w[i].t];
		if (size[w[i].t]>size[big[x]]) big[x]=w[i].t;
	}
}
void dfs1(int x){
	hash[dfn[x]=++cnt]=x;
	if (dfn[x]==dfn[fa[x]]+1) link[x]=link[fa[x]];
		else link[x]=x;
	if (big[x]) dfs1(big[x]);
	for (int i=head[x];i;i=next[i])
	if (w[i].t!=big[x]&&w[i].t!=fa[x]) dfs1(w[i].t);
}
//维护树剖 
int a[N];
void Add(int p,int d){
	for (;p<=n;p+=(p&-p)) a[p]+=d;
}
int sum(int r){
	int ans=0;
	for (;r;r-=(r&-r)) ans+=a[r];
	return ans;
}
inline void swap(int &x,int &y){int z=x;x=y;y=z;}
inline void add(int x,int y,int d){//一条[x,y]线段,O(log^2n) 
	Add(1,d);
	while (link[x]!=link[y]){
		if (h[link[x]]<h[link[y]]) swap(x,y);
		Add(dfn[link[x]],-d);
		Add(dfn[x]+1,d);
		x=fa[link[x]];
	}
	if (h[x]<h[y]) swap(x,y);
	Add(dfn[y],-d);
	Add(dfn[x]+1,d);
}
//分治 
struct qs{int type,a,b,v,id,k;}q[N];
int ans[N];
inline bool cmp(const qs &x,const qs &y){
	return x.k==y.k?x.id<y.id:x.k<y.k;
}
void solve(int L,int R,int l,int r){//O(logn)
	if (l>r) return;
	if (L==R){
		for (int i=l;i<=r;i++)
		if (q[i].type==2) ans[q[i].id]=L;
		return;
	}
	int M=(L+R)/2,t=l-1;
	for (int i=l;i<=r;i++){
		if (!q[i].type){
			if (q[i].v>M) add(q[i].a,q[i].b,1),q[i].k=1;
				else t++,q[i].k=0;
		}
		if (q[i].type==1){
			if (q[i].v>M) add(q[i].a,q[i].b,-1),q[i].k=1;
				else t++,q[i].k=0;
		}
		if (q[i].type==2){
			int s=sum(dfn[q[i].v]);
			if (s>0) q[i].k=1;//存在大于M的 
				else t++,q[i].k=0;
		}
	}
	for (int i=l;i<=r;i++){
		if (!q[i].type&&q[i].v>M) add(q[i].a,q[i].b,-1);
		if (q[i].type==1&&q[i].v>M) add(q[i].a,q[i].b,1);
	}
	sort(q+l,q+r+1,cmp);
	solve(L,M,l,t);solve(M+1,R,t+1,r);
}
inline int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
int main()
{
	freopen("network_tenderRun.in","r",stdin);
	freopen("network_tenderRun.out","w",stdout);
	n=read();m=read();
	for (int i=1;i<n;i++){
		w[i].f=read();w[i].t=read();
		w[i+n].t=w[i].f;w[i+n].f=w[i].t;
		add(w[i].f,i);add(w[i].t,i+n);
	}
	fa[1]=h[1]=1;dfs(1);dfs1(1);
	int M=0;
	for (int i=1;i<=m;i++){
		q[i].type=read();
		q[i].id=i;
		if (!q[i].type){
			q[i].a=read();
			q[i].b=read();
			q[i].v=read();
			M=max(M,q[i].v);
		}
		if (q[i].type==1){
			int t=read();
			q[i].a=q[t].a;
			q[i].b=q[t].b;
			q[i].v=q[t].v;
		}
		if (q[i].type==2) q[i].v=read();
	}
	memset(ans,-1,sizeof ans);
	solve(0,M,1,m);
	for (int i=1;i<=m;i++)
	if (ans[i]!=-1) printf("%d\n",ans[i]?ans[i]:-1);
	return 0;
}