A Not allowed system call求助
  • 板块学术版
  • 楼主Gary88
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/11/23 14:49
  • 上次更新2023/11/5 07:28:26
查看原帖
A Not allowed system call求助
104963
Gary88楼主2020/11/23 14:49
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int n,m,e[600001],f[600001],t[600001],s[600001],p,h[600001],cnt,id[600001],num[600001];
long long sum[5000001],la[5000001],mod=1e9+7;
struct ppp
{
    int to,ne;
}a[500001];
void add(int x,int y)
{
    a[++p].to=y;
    a[p].ne=h[x];
    h[x]=p;
}
void dfs(int x)
{
    s[x]=1;
    int maxsize=0,now=0;
    for(int i=h[x];i;i=a[i].ne)
    {
        dfs(a[i].to);
        s[x]+=s[a[i].to];
        if(s[a[i].to]>maxsize)
        {
            maxsize=s[a[i].to];
            now=a[i].to;
        }
    }
    e[x]=now;
}
void ddfs(int x,int top)
{
    id[x]=++cnt;
    num[cnt]=x;
    t[x]=top;
    if(e[x]==0)
    return;
    ddfs(e[x],top);
    for(int i=h[x];i;i=a[i].ne)
    {
        if(a[i].to!=e[x])
        ddfs(a[i].to,a[i].to);
    }
}
void add(int l,int r,int rt,int L,int R,long long k)
{
    if(L<=l&&r<=R)
    {
        la[rt]+=k;
        sum[rt]+=k*(r-l+1);
        la[rt]%=mod;
        sum[rt]%=mod;
        return;
    }
    int mid=(l+r)>>1;
    sum[rt<<1]+=la[rt]*(mid-l+1);
    sum[rt<<1|1]+=la[rt]*(r-mid);
    la[rt<<1]+=la[rt];
    la[rt<<1|1]+=la[rt];
    sum[rt<<1]%=mod;
    sum[rt<<1|1]%=mod;
    la[rt<<1]%=mod;
    la[rt<<1|1]%=mod;
    la[rt]=0;
    if(L<=mid)
    add(l,mid,rt<<1,L,R,k);
    if(R>mid)
    add(mid+1,r,rt<<1|1,L,R,k);
    sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;
}
long long ask(int l,int r,int rt,int L,int R)
{
    if(L<=l&&r<=R)
    {
        return sum[rt];
    }
    int mid=(l+r)>>1;
    sum[rt<<1]+=la[rt]*(mid-l+1);
    sum[rt<<1|1]+=la[rt]*(r-mid);
    la[rt<<1]+=la[rt];
    la[rt<<1|1]+=la[rt];
    sum[rt<<1]%=mod;
    sum[rt<<1|1]%=mod;
    la[rt<<1]%=mod;
    la[rt<<1|1]%=mod;
    la[rt]=0;
    long long ans=0;
    if(L<=mid)
    ans=(ans+ask(l,mid,rt<<1,L,R))%mod;
    if(R>mid)
    ans=(ans+ask(mid+1,r,rt<<1|1,L,R))%mod;
    return ans;
}
long long query(int x)
{
    if(t[x]==1)
    return ask(1,n,1,id[t[x]],id[x]);
    return (ask(1,n,1,id[t[x]],id[x])+query(f[t[x]]))%mod;
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&f[i]);
        add(f[i],i);
    }
    dfs(1);
    ddfs(1,1);
    scanf("%d",&m);
    while(m--)
    {
        int x,k;
        long long y,z;
        scanf("%d",&k);
        if(k==1)
        {
            scanf("%d%lld%lld",&x,&y,&z);
            add(1,n,1,id[x],id[x],y+z);
            add(1,n,1,id[x],id[x]+s[x]-1,-z);
        }
        else
        {
            scanf("%d",&x);
            printf("%lld\n",(query(x)+mod)%mod);
        }
    }
}

2020/11/23 14:49
加载中...