1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
| #include <bits/stdc++.h> using namespace std; const int maxn=2e5+5; int val[maxn],d[maxn],f[maxn][35]; vector<array<int,3>> q; struct node { int mx,pmx,smx; int mn,pmn,smn; int sum; }g[maxn][35]; node operator + (const node& a,const node& b) { node c; c.mx=max({a.mx,b.mx,a.smx+b.pmx}); c.pmx=max(a.pmx,a.sum+b.pmx); c.smx=max(b.smx,b.sum+a.smx); c.mn=min({a.mn,b.mn,a.smn+b.pmn}); c.pmn=min(a.pmn,a.sum+b.pmn); c.smn=min(b.smn,b.sum+a.smn); c.sum=a.sum+b.sum; return c; } node reverse(const node& a) { node c=a; swap(c.pmx,c.smx); swap(c.pmn,c.smn); return c; } bool query(int u,int v,int k) { if(d[u]<d[v]) swap(u,v); int dis=d[u]-d[v]; node l{},r{},ans; for(int i=0;i<30;i++) { if(dis&1) { l=l+g[u][i]; u=f[u][i]; } dis>>=1; } if(u==v) ans=l+reverse(g[u][0]); else { for(int i=29;i>=0;i--) { if(f[u][i]!=f[v][i]) { l=l+g[u][i],r=r+g[v][i]; u=f[u][i],v=f[v][i]; } } int lca=f[u][0]; l=l+g[u][0],r=r+g[v][0]; ans=l+g[lca][0]+reverse(r); } return ans.mn<=k&&k<=ans.mx; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t;cin>>t; while(t--) { int n;cin>>n; q.clear(); int cur=0;val[++cur]=1; for(int i=1;i<=n;i++) { char c;cin>>c; if(c=='+') { int v,x;cin>>v>>x; val[++cur]=x; f[cur][0]=v; d[cur]=d[v]+1; } else { int u,v,k;cin>>u>>v>>k; q.push_back({u,v,k}); } } for(int i=1;i<=cur;i++) if(val[i]==1) g[i][0]=node{1,1,1,0,0,0,1}; else g[i][0]=node{0,0,0,-1,-1,-1,-1}; for(int i=1;i<=cur;i++) for(int j=1;j<30;j++) { f[i][j]=f[f[i][j-1]][j-1]; if(f[i][j-1]!=f[i][j]) g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1]; } for(auto i:q) cout<<(query(i[0],i[1],i[2])?"YES":"NO")<<'\n'; } return 0; }
|