觉得每次只会增加log个节点，树剖每次有log段只会使空间复杂度变为 $O(n \times log^2n)$,为啥MLE+RE了呢？

#include<bits/stdc++.h>
#define ls tr[u].l
#define rs tr[u].r
using namespace std;
const int N=1e5+10,mod=20160501;
vector<int> e[N];
int dfn[N],sz[N],ts;
int dep[N],fa[N],son[N],top[N],seq[N];
struct node
{
	int l,r;
	int sum0,sum1,sum2;
	int add;
}tr[N*130];
int root[N],idx;
int a[N];
int w[N],w2[N];
int n,m;

void init(){
	for(int i=1;i<=n;i++)
	{
		w[i]=dep[seq[i]],w2[i]=w[i]*w[i]%mod;
		w[i]=(w[i-1]+w[i])%mod,w2[i]=(w2[i-1]+w2[i])%mod;
	}
}

int is0(int a,int b,int c,int d){
	return min(b,d)-max(a,c)+1;
}

int is1(int a,int b,int c,int d){
	return (w[min(b,d)]-w[max(a,c)-1]+mod)%mod;
}

int is2(int a,int b,int c,int d){
	return (w2[min(b,d)]-w2[max(a,c)-1]+mod)%mod;
}

void pushup(node &root,node left,node right){
	root.sum0=(left.sum0+right.sum0)%mod;
	root.sum1=(left.sum1+right.sum1)%mod;
	root.sum2=(left.sum2+right.sum2)%mod;
}

void pushup(int u){
	pushup(tr[u],tr[ls],tr[rs]);
}

int build(int l,int r){
	int u=++idx;
	if(l==r) 
	{
		tr[u].sum0=a[seq[l]];
		tr[u].sum1=tr[u].sum0*((w[l]-w[l-1]+mod)%mod)%mod;
		tr[u].sum2=tr[u].sum0*((w2[l]-w2[l-1]+mod)%mod)%mod;
		return u;
	}
	int mid=l+r>>1;
	ls=build(l,mid),rs=build(mid+1,r);
	pushup(u);
	return u;
}

int modify(int p,int l,int r,int pl,int pr,int c){
	int u=++idx;
	tr[u]=tr[p];
	tr[u].sum0=(tr[u].sum0+c*is0(l,r,pl,pr)%mod)%mod;
	tr[u].sum1=(tr[u].sum1+c*is1(l,r,pl,pr)%mod)%mod;
	tr[u].sum2=(tr[u].sum2+c*is2(l,r,pl,pr)%mod)%mod;
	if(l>=pl&&r<=pr) tr[u].add+=c;
	else
	{
		int mid=l+r>>1;
		if(pl<=mid) ls=modify(tr[p].l,l,mid,pl,pr,c);
		if(pr>mid) rs=modify(tr[p].r,mid+1,r,pl,pr,c); 
	}
	return u;
}

node query(int u,int l,int r,int pl,int pr,int c){
	if(l>=pl&&r<=pr) 
	{
		node res=tr[u];
		res.sum0=(res.sum0+(r-l+1)*c%mod)%mod;
		res.sum1=(res.sum1+(w[r]-w[l-1]+mod)*c%mod)%mod;
		res.sum2=(res.sum2+(w2[r]-w2[l-1]+mod)*c%mod)%mod;
		return res;
	}
	c+=tr[u].add;
	int mid=l+r>>1;
	node res={0,0,0,0,0,0};
	if(pl<=mid) pushup(res,res,query(ls,l,mid,pl,pr,c));
	if(pr>mid) pushup(res,res,query(rs,mid+1,r,pl,pr,c));
	return res;
}

void dfs1(int u,int p,int d){
    dep[u]=d,fa[u]=p,sz[u]=1;
    for(auto v:e[u])
    {
        if(v==p) continue;
        dfs1(v,u,d+1);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}

void dfs2(int u,int t){
    dfn[u]=++ts,top[u]=t,seq[dfn[u]]=u;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(auto v:e[u])
    {
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

void modify_path(int i,int u,int v,int c){
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		root[i]=modify(root[i],1,n,dfn[top[u]],dfn[u],c);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]) swap(u,v);
	root[i]=modify(root[i],1,n,dfn[v],dfn[u],c);
}

int query_path(int i,int u,int v){
	int t0=0,y0=dep[v],y1=dep[v];
	int ans[2][3];
	memset(ans,0,sizeof ans);
	int res=0;
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v),t0^=1;
		node t=query(root[i],1,n,dfn[top[u]],dfn[u],0);
		ans[t0][0]=(ans[t0][0]+t.sum0)%mod;
		ans[t0][1]=(ans[t0][1]+t.sum1)%mod;
		ans[t0][2]=(ans[t0][2]+t.sum2)%mod;
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]) swap(u,v),t0^=1;
	int anc=v;
	node t=query(root[i],1,n,dfn[v],dfn[u],0);
	ans[t0][0]=(ans[t0][0]+t.sum0)%mod;
	ans[t0][1]=(ans[t0][1]+t.sum1)%mod;
	ans[t0][2]=(ans[t0][2]+t.sum2)%mod;
	
	y0=(y0-2*dep[anc]+mod)%mod;
	res=(res+ans[0][2]+ans[1][2])%mod;
	res=(res+ans[0][1]*(2*y0+1)%mod+mod)%mod;
	res=(res-ans[1][1]*(2*y1+1)%mod+mod)%mod;
	res=(res+ans[0][0]*(y0*y0%mod+y0)%mod+mod)%mod;
	res=(res+ans[1][0]*(y1*y1%mod+y1)%mod+mod)%mod;
	
	return res*((mod+1)/2)%mod;
}

signed main()
{
	cin>>n>>m;
	
	for(int i=1,x,y;i<n;i++)
	{
		cin>>x>>y;
		e[x].push_back(y),e[y].push_back(x); 
	}
	
	dfs1(1,0,1);
	dfs2(1,1);
	
	init();
	for(int i=1;i<=n;i++) cin>>a[i];
	
	root[0]=build(1,n);
	int now=0,lastans=0;
	for(int i=1,t,x,y,d;i<=m;i++)
	{
		cin>>t;
		if(t==1)
		{
			now++,root[now]=root[now-1];
			cin>>x>>y>>d;
			x=x^lastans,y=y^lastans;
			modify_path(now,x,y,d);
		}
		if(t==2)
		{
			cin>>x>>y;
			x=x^lastans,y=y^lastans;
			lastans=query_path(now,x,y);
			cout<<lastans<<"\n";
		}
		if(t==3)
		{
			cin>>x;
			x=x^lastans;
			now=x;
		}
	} 
}