QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133774#4941. Tree Beautynameless_story#RE 4ms30056kbC++173.6kb2023-08-02 13:58:552023-08-02 13:58:57

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 13:58:57]
  • 评测
  • 测评结果:RE
  • 用时:4ms
  • 内存:30056kb
  • [2023-08-02 13:58:55]
  • 提交

answer

#pragma GCC optimize(2)
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
const int N=200005;
int n,m;
int dfn[N],trid[N],maxd[N],ind,hson[N],som[N],deep[N],dad[N];
int dnum[N];
vector<int> V[N],num[N],nom[N],fum[N];
void dfs1(int u,int fa)
{
    deep[u]=deep[fa]+1;
    dnum[deep[u]]++;
    som[u]=1;
    dad[u]=fa;
    for(int v:V[u])
    {
        if(v==fa)
        continue;
        dfs1(v,u);
        som[u]=som[v]+som[u];
        if(maxd[v]+1>maxd[u])
        maxd[u]=maxd[v]+1,hson[u]=v;
    }
}
void dfs2(int u,int fa)
{
    dfn[u]=++ind;
    trid[ind]=u;
    if(!hson[u])
    {
        num[u].pb(1);
        for(int i=1;i<=20&&i<=num[u].size();i++)
        nom[u].pb(num[u][num[u].size()-i]),fum[u].pb(0);
        return;
    }
    dfs2(hson[u],u);
    num[u].swap(num[hson[u]]);
    num[u].pb(1);
    for(int v:V[u])
    {
        if(v==fa||v==hson[u])
        continue;
        dfs2(v,u);
        assert(num[v].size()<num[u].size());
        for(int i=1;i<=num[v].size();i++)
        num[u][num[u].size()-1-i]+=num[v][num[v].size()-i];
    }
    for(int i=1;i<=20&&i<=num[u].size();i++)
    nom[u].pb(num[u][num[u].size()-i]),fum[u].pb(0);
}
struct node
{
    ll v,lazy;
}tree[N<<2];
#define lc pos<<1
#define rc pos<<1|1
void frog(int pos,int l,int r,ll k)
{
    tree[pos].v+=k*(r-l+1);
    tree[pos].lazy+=k;
}
void pushdown(int pos,int l,int r)
{
    int mid=l+r>>1;
    frog(lc,l,mid,tree[pos].lazy);
    frog(rc,mid+1,r,tree[pos].lazy);
    tree[pos].lazy=0;
}
void modify(int pos,int l,int r,int nl,int nr,ll k)
{
    assert(nl<=nl&&nl>=1&&nr<=n);
    if(l>=nl&&r<=nr)
    {
        tree[pos].v+=k*(r-l+1);
        tree[pos].lazy+=k;
        return;
    }
    int mid=l+r>>1;
    pushdown(pos,l,r);
    if(nl<=mid)
    modify(lc,l,mid,nl,nr,k);
    if(nr>mid)
    modify(rc,mid+1,r,nl,nr,k);
    tree[pos].v=tree[lc].v+tree[rc].v;
}
ll seek(int pos,int l,int r,int nl,int nr)
{
    if(l>=nl&&r<=nr)
    {
        return tree[pos].v;
    }
    int mid=l+r>>1;
    ll ret=0;
    pushdown(pos,l,r);
    if(nl<=mid)
    ret+=seek(lc,l,mid,nl,nr);
    if(nr>mid)
    ret+=seek(rc,mid+1,r,nl,nr);
    return ret;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=2;i<=n;i++)
    {
        int p;
        cin>>p;
        V[p].pb(i);
    }
    dfs1(1,0);
    dfs2(1,0);
    // for(int i=1;i<=n;i++)
    // cerr<<num[i].size()<<'\n';
    while(m--)
    {
        int opt;
        cin>>opt;
        if(opt==1)
        {
            int x,y,K;
            cin>>x>>y>>K;
            if(K==1)
            {
                modify(1,1,n,dfn[x],dfn[x]+som[x]-1,y);
            }
            else
            {
                ll ret=0;
                for(int i=0;i<nom[x].size();i++)
                {
                    ret+=nom[x][i]*1ll*y;
                    fum[x][i]+=y;
                    y/=K;
                }
                modify(1,1,n,dfn[x],dfn[x],ret);
            }
        }
        else
        {
            int x;
            cin>>x;
            ll out=0;
            out=seek(1,1,n,dfn[x],dfn[x]+som[x]-1);
            vector fume(nom[x].size(),0);
            for(int i=1,up=dad[x];i<=20&&up;i++,up=dad[up])
            {
                for(int j=i;j<nom[up].size();j++)
                assert(j-i<fume.size()),fume[j-i]+=fum[up][j];
            }
            for(int i=0;i<nom[x].size();i++)
            out+=nom[x][i]*1ll*fume[i];
            cout<<out<<'\n';
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 23968kb

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: 0ms
memory: 30056kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Dangerous Syscalls

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: