提交时间:2024-07-30 18:55:30

运行 ID: 30826

#include<bits/stdc++.h> #define jp8 push_back #define mid (l+r)/2 #define ls p*2 #define rs p*2+1 using namespace std; const int N=2e5+20; int mod=1e9+7; vector<int> e[N]; struct nd{ int a,b; };vector<nd> opt[N]; int dfn[N],rk[N],siz[N],dep[N]; struct seg{ long long t[N<<2],c[N<<2]; void pd(int p){ t[ls]+=t[p];t[rs]+=t[p];t[p]=0;t[ls]%=mod,t[rs]%=mod; c[ls]+=c[p];c[rs]+=c[p];c[p]=0;c[ls]%=mod,c[rs]%=mod; }void upd(int p,int l,int r,int pl,int pr,int a,int b){ if(pl<=l&&r<=pr){ t[p]+=a,c[p]+=b; t[p]%=mod,c[p]%=mod; return ; }pd(p); if(pl<=mid)upd(ls,l,mid,pl,pr,a,b); if(pr>mid)upd(rs,mid+1,r,pl,pr,a,b); }int qry(int p,int l,int r,int x){ //if(l==r) cout<<t[p]<<' '<<c[p]<<' '<<rk[l]<<"II"<<endl; if(l==r) return 1ll*(1ll*t[p]*dep[rk[l]]%mod+c[p])%mod*(-(dep[rk[l]]%2)*2+1+mod)%mod; pd(p); if(x<=mid) return qry(ls,l,mid,x); if(x>mid) return qry(rs,mid+1,r,x); } }SGT1;bool vis[N];int dfncnt=0; void dfs(int u){ //cout<<u<<endl; vis[u]=1;siz[u]=1;dfn[u]=++dfncnt;rk[dfncnt]=u; for(auto v:e[u]){ if(vis[v]) continue;dep[v]=dep[u]+1;dfs(v);siz[u]+=siz[v]; } } int n,m;set<int> dt; int main(){ cin>>n>>m; for(int i=2;i<=n;i++){ int fa;cin>>fa; e[i].jp8(fa); e[fa].jp8(i); }dep[1]=1;dfs(1); for(int i=1;i<=m;i++){ int op;cin>>op; if(op==1){ int a,b,x; cin>>x>>a>>b; dt.insert(dfn[x]);a-=b*dep[x]%mod;a+=mod;a%=mod; if(dep[x]%2==1) a=mod-a,b=mod-b; //cout<<dfn[x]<<' '<<siz[x]<<"II"<<endl; //cout<<a<<' '<<b<<"II"<<endl; swap(a,b); SGT1.upd(1,1,n,dfn[x],dfn[x]+siz[x]-1,a,b); opt[dfn[x]].jp8((nd){mod-a,mod-b}); }if(op==2){ int x;cin>>x; cout<<SGT1.qry(1,1,n,dfn[x])<<endl; }if(op==3){ int x;cin>>x; auto it=dt.lower_bound(dfn[x]); if(it!=dt.end()){ while(it!=dt.end()&&*it<dfn[x]+siz[x]){ int s=*it;//cout<<s<<endl; for(auto ed:opt[s]){ //cout<<ed.a<<' '<<ed.b<<"II"<<s<<' '<<s+siz[rk[s]]-1<<endl; SGT1.upd(1,1,n,s,s+siz[rk[s]]-1,ed.a,ed.b); }opt[s].clear(); dt.erase(s); it=dt.lower_bound(s); } } } } return 0; }