#include<bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" #define int long long const int N=2e5+5; const int INF = 0x3f3f3f3f; // 假设一个区间的最大字段和为 max 最小字段和为 min // 那么 [min,max]区间的数都可以取到，即都存在对应的子区间。因为点权仅为 1 或 −1 // 一个子区间左右扩张，其值只会加一或者减一，不会跳跃，而初始值为 0 //后面就非常简单了，直接树剖 std::vector<int>edge[N]; struct op{ char opr; int x,y,v; }a[N]; int val[N],now_n; // int n,v[N],sz[N],son[N],dist[N],father[N]; //求子树大小，重儿子，深度，父亲 void Dfs(int x,int fa){ sz[x]=1; for(auto y:edge[x]){ if(y==fa)continue; dist[y]=dist[x]+1; father[y]=x; Dfs(y,x); sz[x]+=sz[y]; if(sz[y]>sz[son[x]])son[x]=y; } } int now_dfn,l_dfn[N],r_dfn[N],pos_dfn[N],top[N]; //对于每个点重新编号，同时维护出重链最顶上的点，还有dfn序 //编号顺序就是求在dfn序是加入一个限制，先走重链（从同一点出发子树大的路径） void DFS(int x,int fa,int tp){ l_dfn[x]=++now_dfn;pos_dfn[now_dfn]=x;top[x]=tp; if(son[x])DFS(son[x],x,tp); for(auto y:edge[x]){ if(y!=fa&&y!=son[x])DFS(y,x,y); } r_dfn[x]=now_dfn; } struct Node{ int maxn,l_maxn,r_maxn; int minn,l_minn,r_minn; int sum; }Tree[N*4]; void pushup(Node &now,Node &l,Node &r){ now.sum=l.sum+r.sum; now.maxn=max(l.r_maxn+r.l_maxn,max(l.maxn,r.maxn)); now.minn=min(l.r_minn+r.l_minn,min(l.minn,r.minn)); now.l_maxn=max(l.l_maxn,l.sum+r.l_maxn); now.r_maxn=max(r.r_maxn,r.sum+l.r_maxn); now.l_minn=min(l.l_minn,l.sum+r.l_minn); now.r_minn=min(r.r_minn,r.sum+l.r_minn); } void pushup(int now){ pushup(Tree[now],Tree[now*2],Tree[now*2+1]); } void build(int now,int l,int r){ if(l==r){ Tree[now].maxn=Tree[now].l_maxn=Tree[now].r_maxn=val[pos_dfn[l]]; Tree[now].minn=Tree[now].l_minn=Tree[now].r_minn=val[pos_dfn[l]]; Tree[now].sum=val[pos_dfn[l]]; return; } int mid=(l+r)>>1; build(now*2,l,mid); build(now*2+1,mid+1,r); pushup(now); } Node qurey(int now,int l,int r,int x,int y){ if(x<=l&&y>=r)return Tree[now]; int mid=(l+r)>>1; if(y<=mid)return qurey(now*2,l,mid,x,y); if(x>mid)return qurey(now*2+1,mid+1,r,x,y); Node ans; Node ls=qurey(now*2,l,mid,x,y); Node rs=qurey(now*2+1,mid+1,r,x,y); pushup(ans,ls,rs); return ans; } Node calc(int x,int y){ //这里不能用INT_MAX,INT_MIN 会爆 Node left={-INF,-INF,-INF,INF,INF,INF,0}; Node right=left; while(top[x]!=top[y]){ if(dist[top[x]]<dist[top[y]])swap(x,y),swap(left,right); Node now=qurey(1,1,now_n,l_dfn[top[x]],l_dfn[x]); Node t=left; //树链向上跳，显然now的dfn序会更小 pushup(left,now,t); x=father[top[x]]; } if(dist[x]<dist[y])swap(x,y),swap(left,right); Node t=left; Node now=qurey(1,1,now_n,l_dfn[y],l_dfn[x]); pushup(left,now,t); swap(left.r_maxn,left.l_maxn); swap(left.r_minn,left.l_minn); Node ans; pushup(ans,left,right); return ans; } signed main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int T=1;cin>>T; while(T--){ cin>>n; for(int i=0;i<=n+5;i++)edge[i].clear(),son[i]=0; now_n=1;val[1]=1;now_dfn=0;dist[1]=0; for(int i=1;i<=n;i++){ cin>>a[i].opr; if(a[i].opr=='+'){ cin>>a[i].y>>a[i].v; edge[a[i].y].push_back(++now_n); val[now_n]=a[i].v; } else cin>>a[i].x>>a[i].y>>a[i].v; } Dfs(1,1);DFS(1,1,1); build(1,1,now_n); for(int i=1;i<=n;i++){ if(a[i].opr=='+')continue; int x=a[i].x,y=a[i].y,v=a[i].v; if(x==y){ if(v==0||v==val[x])cout<<"YES"<<endl; else cout<<"NO"<<endl; continue; } Node ans=calc(x,y); ans.minn=min(0ll,ans.minn); ans.maxn=max(0ll,ans.maxn); if(v>=ans.minn&&v<=ans.maxn)cout<<"YES"<<endl; else cout<<"NO"<<endl; } } return 0; }