记录编号	397426	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]榴莲	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.846 s
提交时间	2017-04-20 13:59:34	内存使用	85.17 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int n,m,w[N],head[N],next[N];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int fa[N],s[N],big[N],link[N],dfn[N];
void dfs(int x){
	s[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i]]){
		int v=w[i];
		fa[v]=x;
		dfs(v);
		s[x]+=s[v];
		if (s[v]>s[big[x]]) big[x]=v;
	}
}
void po(int x){
	static int cnt=0;
	dfn[x]=++cnt;
	link[x]=(dfn[x]==dfn[fa[x]]+1?link[fa[x]]:x);
	if (!big[x]) return;
	po(big[x]);
	for (int i=head[x];i;i=next[i])
	if (w[i]!=big[x]&&w[i]!=fa[x]) po(w[i]);
}
int lca(int x,int y){
	for (;link[x]!=link[y];x=fa[link[x]])
		if (dfn[link[x]]<dfn[link[y]]) swap(x,y);
	return dfn[x]<dfn[y]?x:y;
}
struct bit{
	int a[N];
	void add(int p,int d){
		for (;p<=n;p+=p&-p) a[p]+=d;
	}
	int sum(int p){
		int ans=0;
		for (;p;p-=p&-p) ans+=a[p];
		return ans;
	}
	int sum(int l,int r){
		return sum(r)-sum(l-1);
	}
}T1,T2;
struct opt{int tp,p,d,w;bool lr;}Q[N];
int que[N],Que[N],size;
//tp=1表示在T1中[l,r]+d,tp=2表示在T2中[l,r]+d,tp=3表示询问 
int ans[N],q,tp[N],x[N],y[N],d[N];
bool cmp(int x,int y){
	return Q[x].lr==Q[y].lr?x<y:Q[x].lr<Q[y].lr;
}
void solve(int l,int r,int L,int R){
	if (l>r) return;
	if (L==R){
		for (int i=l;i<=r;i++)
			if (Q[que[i]].tp==3) ans[que[i]]=L;
		return;
	}
	int mid=(L+R)>>1,pos=l-1;
	for (int i=l;i<=r;i++){
		int id=que[i];
		int tp=Q[id].tp,p=Q[id].p,d=Q[id].d;
		if (tp==3){
			int S=T1.sum(dfn[p],dfn[p]+s[p]-1)+T2.sum(dfn[p]);
			if (S<Q[id].d) Q[id].d-=S,Q[id].lr=0,pos++;
				else Q[id].lr=1;
		}
		if (tp==1){
			if (Q[id].w>mid) T1.add(p,d),Q[id].lr=1;
			else Q[id].lr=0,pos++;
		}
		if (tp==2){
			if (Q[id].w>mid) T2.add(p,d),Q[id].lr=1;
			else Q[id].lr=0,pos++;
		}
	}
	for (int i=l;i<=r;i++){
		int id=que[i];
		if (Q[id].w<=mid) continue;
		if (Q[id].tp==1) T1.add(Q[id].p,-Q[id].d);
		if (Q[id].tp==2) T2.add(Q[id].p,-Q[id].d);
	}
	size=0;
	for (int i=l;i<=r;i++)
		if (!Q[que[i]].lr) Que[++size]=que[i];
	for (int i=l;i<=r;i++)
		if (Q[que[i]].lr) Que[++size]=que[i];
	for (int i=r;i>=l;i--) que[i]=Que[size--];
	solve(l,pos,L,mid);solve(pos+1,r,mid+1,R);
}
bool ask[N];
void push(int x,int y,int d,int w){
	int LCA=lca(x,y);
	q++;Q[q]=(opt){1,dfn[x],d,w,false};
	q++;Q[q]=(opt){1,dfn[y],d,w,false};
	q++;Q[q]=(opt){1,dfn[LCA],-d,w,false};
	if (LCA==1) return;
	q++;Q[q]=(opt){1,dfn[fa[LCA]],-d,w,false};
}
void push(int x,int d,int w){
	q++;Q[q]=(opt){2,dfn[x],d,w,false};
	q++;Q[q]=(opt){2,dfn[x]+s[x],-d,w,false};
}
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("Durio_zibethinus_Murr.in","r",stdin);
	freopen("Durio_zibethinus_Murr.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<n;i++){
		int x=read(),y=read();
		add(x,y);add(y,x);
	}
	int Max=0;
	fa[1]=1;dfs(1);po(1);
	for (int i=1;i<=m;i++){
		tp[i]=read();
		if (tp[i]==1){
			x[i]=read();y[i]=read();d[i]=read();
			push(x[i],y[i],1,d[i]);
		}
		if (tp[i]==2){
			x[i]=read();d[i]=read();
			push(x[i],1,d[i]);
		}
		if (tp[i]==3){
			int id=read();
			if (tp[id]==1) push(x[id],y[id],-1,d[id]);
				else push(x[id],-1,d[id]);
		}
		if (tp[i]==4){
			x[i]=read();d[i]=read();
			ask[++q]=1;
			Q[q]=(opt){3,x[i],d[i],false};
		}
		Max=max(Max,d[i]);
	}
	for (int i=1;i<=q;i++) que[i]=i;
	solve(1,q,0,Max);
	for (int i=1;i<=q;i++)
		if (ask[i]) printf("%d\n",ans[i]?ans[i]:-1);
	return 0;
}