RT，为什么这里是RE on #3 但CF上是　TLE on #3 同时求调树剖 。https://www.luogu.com.cn/record/130292710

https://codeforces.com/contest/1843/submission/228515163

#include <bits/stdc++.h>

using namespace std;

const int maxn=2e5+5;

int n,m,rt,mod,a[maxn],f[maxn],cnt2=1;
int h[maxn],e[maxn],ne[maxn],idx;
int at[maxn],top[maxn],siz[maxn];
int cnt=0,son[maxn],dep[maxn],id[maxn];

struct qu
{
	int opt,l,r,k;
}q[maxn];

struct rnode
{
	int l,r,ls,rs,maxx,ls2,rs2,minn,sum;
}tre[maxn<<2];

void print(rnode x)
{
	cout<<x.ls<<" "<<x.rs<<" "<<x.maxx<<" "<<x.ls2<<" "<<x.rs2<<" "<<x.minn<<" "<<x.sum<<endl;
}


void add(int u,int v)
{
	e[idx]=v,ne[idx]=h[u],h[u]=idx++;
}

rnode push_up(rnode x,rnode y)
{
	rnode ans={0,0,0,0,0,0,0,0,0};
	ans.sum=x.sum+y.sum;
	ans.ls=max(x.ls,x.sum+y.ls);
	ans.rs=max(y.rs,y.sum+x.rs);
	ans.maxx=max(max(x.maxx,y.maxx),x.rs+y.ls);
	ans.ls2=min(x.ls2,x.sum+y.ls2);
	ans.rs2=min(y.rs2,y.sum+x.rs2);
	ans.minn=min(min(x.minn,y.minn),x.rs2+y.ls2);
	return ans;
}


void push_up(int k)
{
	tre[k].sum=tre[k<<1].sum+tre[k<<1|1].sum;
	tre[k].ls=max(tre[k<<1].ls,tre[k<<1].sum+tre[k<<1|1].ls);
	tre[k].rs=max(tre[k<<1|1].rs,tre[k<<1|1].sum+tre[k<<1].rs);
	tre[k].maxx=max(max(tre[k<<1].maxx,tre[k<<1|1].maxx),tre[k<<1].rs+tre[k<<1|1].ls);
	tre[k].ls2=min(tre[k<<1].ls2,tre[k<<1].sum+tre[k<<1|1].ls2);
	tre[k].rs2=min(tre[k<<1|1].rs2,tre[k<<1|1].sum+tre[k<<1].rs2);
	tre[k].minn=min(min(tre[k<<1].minn,tre[k<<1|1].minn),tre[k<<1].rs2+tre[k<<1|1].ls2);
}



void build(int k,int l,int r)
{
	tre[k].l=l,tre[k].r=r;
	if(l==r)
	{
		tre[k].ls=tre[k].rs=tre[k].ls2=tre[k].rs2=tre[k].maxx=tre[k].minn=tre[k].sum=at[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	push_up(k);
}

void update(int k,int x,int v)
{
	if(tre[k].r==tre[k].l&&tre[k].l==x)
	{
		tre[k].ls=tre[k].rs=tre[k].ls2=tre[k].rs2=tre[k].maxx=tre[k].minn=tre[k].sum=v;
		tre[k].ls=max(tre[k].ls,0),tre[k].rs=max(tre[k].rs,0),tre[k].maxx=max(0,tre[k].maxx);
		tre[k].ls2=min(tre[k].ls2,0),tre[k].rs=min(tre[k].rs,0),tre[k].minn=min(0,tre[k].minn);
		return ;
	}
	int mid=(tre[k].l+tre[k].r)>>1;
	if(x<=mid) update(k<<1,x,v);
	else update(k<<1|1,x,v);
	push_up(k);
}

rnode query(int k,int l,int r)
{
	if(tre[k].l>=l&&tre[k].r<=r) return tre[k];
	int mid=(tre[k].l+tre[k].r)>>1;
	if(r<=mid) return query(k<<1,l,r);
	if(l>mid) return query(k<<1|1,l,r);
	rnode x=query(k<<1,l,r),y=query(k<<1|1,l,r),ans;
	ans.sum=x.sum+y.sum;
	ans.ls=max(x.ls,x.sum+y.ls);
	ans.rs=max(y.rs,y.sum+x.rs);
	ans.maxx=max(max(x.maxx,y.maxx),x.rs+y.ls);
	ans.ls2=min(x.ls2,x.sum+y.ls2);
	ans.rs2=min(y.rs2,y.sum+x.rs2);
	ans.minn=min(min(x.minn,y.minn),x.rs2+y.ls2);
	return ans;
}

void dfs1(int u,int fa)
{
    siz[u]=1;int mx=0,p=-1;
    for(int i=h[u];~i;i=ne[i])
    {
        int v=e[i];
        if(v==fa) continue;
        f[v]=u;
        dep[v]=dep[u]+1;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(mx<siz[v]) mx=siz[v],p=v;
    }
    if(p!=-1) son[u]=p;
}

void dfs2(int u,int fa,int topf)
{
    id[u]=++cnt;
    at[cnt]=a[u];
    top[u]=topf;
    if(!son[u]) return ;
    dfs2(son[u],u,topf);
    for(int i=h[u];~i;i=ne[i])
    {
        int v=e[i];
        if(v==fa||v==son[u]) continue;
        dfs2(v,u,v);
    }
}

void update_l(int x,int v)
{
    update(1,id[x],v);
}


rnode query_l(int l,int r)
{
    rnode ans={0,0,0,0,0,0,0,0,0};
    while(top[l]!=top[r])
    {
        if(dep[top[l]]<dep[top[r]]) swap(l,r);
        ans=push_up(ans,query(1,id[top[l]],id[l]));
//        print(query(1,id[top[l]],id[l]));
        l=f[top[l]];
    }
    if(dep[l]>dep[r]) swap(l,r);
    ans=push_up(query(1,id[l],id[r]),ans);
    return ans;
}


int main()
{
	cin.tie(0) -> sync_with_stdio(0);
	int T;
	cin>>T;
	while(T--)
	{
		for(int i=1;i<=100;i++) h[i]=-1;
		idx=0;
		cnt=0,cnt2=1;
	    a[1]=1;
	    cin>>n;
	    for(int i=1;i<=n;i++)
	    {
	    	char c;
	    	cin>>c;
	    	if(c=='+')
	    	{
	    		int v,x;
	    		cin>>v>>x;
	    		cnt2++;
	    		add(v,cnt2);
	    		add(cnt2,v);
	    		q[i]={1,cnt2,x};
			}
			else
			{
				int l,r,k;
				cin>>l>>r>>k;
				q[i]={0,l,r,k};
			}
		}
		rt=1;
	    dfs1(rt,-1);
	    dfs2(rt,-1,rt);
	    build(1,1,cnt);
	    for(int i=1;i<=n;i++)
	    {
	    	if(q[i].opt==1)
	    	{
	    		update_l(q[i].l,q[i].r);
			}
			else
			{
				int l=q[i].l,r=q[i].r,k=q[i].k;
				rnode ans=query_l(l,r);
				if(ans.maxx>=k&&ans.minn<=k)
				{
					cout<<"YES"<<"\n";
				}
				else cout<<"NO"<<"\n";
			}
		}	
	}
    
    return 0;
}