QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133917#4941. Tree BeautyPlentyOfPenaltyRE 2ms10412kbC++142.6kb2023-08-02 17:29:292023-08-02 17:29:31

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 17:29:31]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:10412kb
  • [2023-08-02 17:29:29]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned un;
ll read()
{
    ll x=0;char c=getchar();
    bool f=0;
    while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f?-x:x;
}
const int MAXN = 100011,L = 18;
std::vector<int>g[MAXN];
int dfn[MAXN],ed[MAXN], fa[MAXN],cur;
void dfs(int u)
{
    dfn[u]=++cur;
    for(auto v:g[u])dfs(v);
    ed[u]=cur;
}
int n,q;
struct Segment_Tree
{
    struct node
    {
        ll sum,tag;
        void pushtag(ll k,ll len)
        {
            sum+=k*len,tag+=k;
        }
    }t[MAXN];
    #define rt t[num]
    #define tl t[num<<1]
    #define tr t[num<<1|1]
    void pushdown(un l,un r,un num)
    {
        if(!rt.tag)return;
        un mid=(l+r)>>1;
        tl.pushtag(rt.tag,mid-l+1);
        tr.pushtag(rt.tag,r-mid);
        rt.tag=0;
    }
    void Add(un ql,un qr,ll k,un l=1,un r=n,un num=1)
    {
        if(ql<=l&&r<=qr)return rt.pushtag(k,r-l+1);
        pushdown(l,r,num);
        un mid=(l+r)>>1;
        if(ql<=mid)Add(ql,qr,k,l,mid,num<<1);
        if(qr>mid)Add(ql,qr,k,mid+1,r,num<<1|1);
        rt.sum=tl.sum+tr.sum;
    }
    ll Qsum(un ql,un qr,un l=1,un r=n,un num=1)
    {
        if(ql<=l&&r<=qr)return rt.sum;
        pushdown(l,r,num);
        ll res=0;
        un mid=(l+r)>>1;
        if(ql<=mid)res+=Qsum(ql,qr,l,mid,num<<1);
        if(qr>mid)res+=Qsum(ql,qr,mid+1,r,num<<1|1);
        return res;
    }
}sgt;
int cnt[MAXN][L];
ll ctrb[MAXN][L];
int main()
{
    n=read(),q=read();
    for(int i=2;i<=n;++i)fa[i]=read(),g[fa[i]].emplace_back(i);
    dfs(1);
    for(int u=1;u<=n;++u)
    {
        int p=u;
        for(int i=0;i<L&&p;++i,p=fa[p])
            ++cnt[p][i];
    }
    while(q--)
    {
        int op=read(),x=read();
        if(op==1)
        {
            int y=read(),k=read();
            if(k==1)sgt.Add(dfn[x],ed[x],y);
            else
            {
                ll tot=0;
                for(int i=0;i<L;++i)
                    ctrb[x][i]+=y,tot+=ll(cnt[x][i])*y,y/=k;
                sgt.Add(dfn[x],dfn[x],tot);
            }
        }
        else
        {
            ll ans=sgt.Qsum(dfn[x],ed[x]);
            //printf("query x=%d,ans=%lld\n",x,ans);
            int p=fa[x];
            for(int i=0;i<L&&p;++i,p=fa[p])
            {
                //printf("p=%d,i=%d\n",p,i);
                for(int j=i+1;j<L;++j)
                    ans+=ctrb[p][j]*cnt[x][j-i-1];
                //printf("new ans = %lld\n",ans);
            }
                
            printf("%lld\n",ans);
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 10412kb

input:

5 5
1 1 3 3
1 1 99 2
2 1
2 3
1 3 2 3
2 3

output:

245
97
99

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 10404kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Runtime Error

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:


result: