Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
30863 | A21μΘ_wjy | 【S】T2 | C++ | 通过 | 100 | 1512 MS | 47648 KB | 1894 | 2024-07-31 09:53:29 |
#include<bits/stdc++.h> #define int long long #define push_back emplace_back #define insert emplace using namespace std; const int mod=1e9+7; const int maxn=2e5+7; int n,m; int C1[maxn]; int C0[maxn]; inline int rp(int x){ return x>=mod?x-mod:x; } inline int lb(int x){ return x&(-x); } inline void add(int x,int dt,int *A){ while(x<=n){ A[x]=rp(A[x]+dt); x+=lb(x); } } inline int qry(int x,int *A){ int ans=0; while(x){ ans=rp(A[x]+ans); x-=lb(x); } return ans; } vector<int> E[maxn]; int fa[maxn]; int dfn[maxn],cnt; int idx[maxn]; int d[maxn]; int siz[maxn]; void dfs(int u){ dfn[u]=++cnt; idx[cnt]=u; siz[u]=1; d[u]=d[fa[u]]+1; for(auto v:E[u]){ if(v==fa[u])continue; dfs(v),siz[u]+=siz[v]; } } vector<int> UC1[maxn]; vector<int> UC0[maxn]; set<int> S; signed main(){ cin>>n>>m; for(int i=2;i<=n;i++){ int x; cin>>x; E[x].push_back(i),E[i].push_back(x); fa[i]=x; } dfs(1); // cout<<"D"<<endl; while(m--){ int op,x; cin>>op>>x; if(op==1){ int d0,d1; cin>>d0>>d1; d0=rp(d0+mod),d1=rp(d1+mod); d0=rp(d0+mod-d1*d[x]%mod); if(d[x]&1)d0=rp(mod-d0),d1=rp(mod-d1); UC0[x].push_back(d0); UC1[x].push_back(d1); S.insert(dfn[x]); add(dfn[x],d0,C0); add(dfn[x]+siz[x],rp(mod-d0),C0); add(dfn[x],d1,C1); add(dfn[x]+siz[x],rp(mod-d1),C1); } else if(op==2){ int res=rp(qry(dfn[x],C0)+qry(dfn[x],C1)*d[x]%mod)%mod; cout<<rp(d[x]&1?mod-res:res)<<endl; } else if(op==3){ for(auto it=S.lower_bound(dfn[x]);it!=S.end()&&(*it)<dfn[x]+siz[x];it=S.erase(it)){ int u=idx[*it]; for(auto t:UC1[u]){ add(dfn[u],rp(mod-t),C1); add(dfn[u]+siz[u],t,C1); } for(auto t:UC0[u]){ add(dfn[u],rp(mod-t),C0); add(dfn[u]+siz[u],t,C0); } UC1[u].clear(),UC0[u].clear(); } } } }