QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134045#4941. Tree Beautywtn135687RE 3ms18068kbC++145.8kb2023-08-02 21:09:292023-08-02 21:10:05

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 21:10:05]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:18068kb
  • [2023-08-02 21:09:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

const int N = 1e5+10,mo = 1e18+7;
inline ll q_pow(int a,int b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mo;
        a=a*a%mo;
        b>>=1;
    }
    return res;
}

int a[N];
int n,q;
vector<int>to[N];
int dfn[N],nfd[N],R[N];
int dep[N];
int fa[N];
int add[21][N];//给下面每层深度的儿子的加
int num[21][N];//每层深度的儿子的数量

// void bfs(){
//     queue<int>q;int cnt=0;dfn[1]=++cnt;nfd[cnt]=1;
//     q.push(1);dep[1]=1;depidR[1]=1;
//     while(q.size()){
//         int u=q.front();q.pop();
//         // cerr<<"u="<<u<<"\n";
//         L[u]=cnt+1;
//         for(int v:to[u]){
//             dep[v]=dep[u]+1;
//             dfn[v]=++cnt;nfd[cnt]=v;
//             depidR[dep[v]]=cnt;
//             q.push(v);
//         }
//         R[u]=cnt;
//     }
// }


void dfs(int u,int fat){
    fa[u]=fat;
    static int cnt;
    dfn[u]=++cnt;
    for(int v:to[u]){
        dfs(v,u);
    }
    R[u]=cnt;
    num[0][u]=1;
    for(int i=1;i<=20;i++)for(int v:to[u])num[i][u]+=num[i-1][v];
    
}


struct XDS {
    
    struct Node{
        int sum;
        int t;
        int len;
    }seg[N<<2];
    inline void setTag(int id,int t,int l,int r){
        int len=r-l+1;
        seg[id].sum+=len*t;
        seg[id].t+=t;
    }
    inline void pushDown(int id,int l,int r){
        int t=seg[id].t;
        if(!t)return;
        int mid=l+r>>1;
        setTag(id<<1,t,l,mid);setTag(id<<1|1,t,mid+1,r);
        seg[id].t=0;
    }
    inline void upDate(int id){
        seg[id].sum=seg[id<<1].sum+seg[id<<1|1].sum;
    }
    void modify(int id,int l,int r,int ql,int qr,int t){
        assert(l<=ql&&qr<=r);
        if(l==ql&&r==qr){setTag(id,t,l,r);return ;}
        pushDown(id,l,r);
        int mid=l+r>>1;
        if(qr<=mid)modify(id<<1,l,mid,ql,qr,t);
        else if(ql>mid)modify(id<<1|1,mid+1,r,ql,qr,t);
        else {
            modify(id<<1,l,mid,ql,mid,t);modify(id<<1|1,mid+1,qr,mid+1,r,t);
        }
        upDate(id);
    }
    ll query(int id,int l,int r,int ql,int qr){
        if(l==qr&&r==qr)return seg[id].sum;
        pushDown(id,l,r);
        int mid=l+r>>1;
        if(qr<=mid)return query(id<<1,l,mid,ql,qr);
        else if(ql>mid)return query(id<<1|1,mid+1,r,ql,qr);
        else return query(id<<1,l,mid,ql,mid)+query(id<<1|1,mid+1,r,mid+1,qr);
    }
    
    // int seg[N << 2], tag[N << 2];
    // void settag(int id, int l, int r, int t){
    //     seg[id] += t * (r - l + 1);
    //     tag[id] += t;
    // }
    // void down(int id, int l, int r){
    //     if(tag[id] == 0) return;
    //     int mid = (l + r) >> 1;
    //     settag(id << 1, l, mid, tag[id]);
    //     settag(id << 1 | 1, mid + 1, r, tag[id]);
    //     tag[id] = 0;
    // }
    // void modify(int id, int l, int r, int ql, int qr, int val){
    //     if(ql == l && qr == r){
    //         settag(id, l, r, val);
    //         return ;
    //     }
    //     int mid = (l + r) >> 1;
    //     down(id, l, r);
    //     if(qr <= mid){
    //         modify(id << 1, l, mid, ql, qr, val);
    //     }else if(ql > mid){
    //         modify(id << 1 | 1, mid + 1, r, ql, qr, val);
    //     }else{
    //         modify(id << 1, l, mid, ql, mid, val);
    //         modify(id << 1 | 1, mid + 1, r, mid + 1, qr, val);
    //     }
    //     seg[id] = seg[id << 1] + seg[id << 1 | 1];
    // }
    // int query(int id, int l, int r, int ql, int qr){
    //     if(ql == l && qr == r) return seg[id];
    //     int mid = (l + r) >> 1;
    //     down(id, l, r);
    //     if(qr <= mid){
    //         return query(id << 1, l, mid, ql, qr);
    //     }else if(ql > mid){
    //         return query(id << 1 | 1, mid + 1, r, ql, qr);
    //     }else{
    //         return query(id << 1, l, mid, ql, mid) + query(id << 1 | 1, mid + 1, r, mid + 1, qr);
    //     }    
    // }

    // void modify(int x,int y,int k){
    //     if(k==1){modify(1,1,n,dfn[x],R[x],y);return ;}
    //     int sum=0;
    //     for(int i=0;i<=20;i++){
    //         if(y<q_pow(k,i))break;
    //         add[i][x]+=(y/q_pow(k,i));
    //         sum+=num[i][x]*(y/q_pow(k,i));
    //     }
    //     modify(1,1,n,dfn[x],dfn[x],sum);
    // }
    
    
    void modify(int x, int y, int k){
        if(k == 1) {
            modify(1, 1, n, dfn[x], R[x], y);
            return;
        }
        int sum = 0;
        add[0][x] += y;
        sum = y;
        for(int i = 1, val = y / k; i <= 20 && val; i ++, val /= k){
            add[i][x] += val;
            sum += val * num[i][x];
        }
        // cout << sum << "qaq\n";
        modify(1, 1, n, dfn[x], dfn[x], sum);
    }
    ll query(int x){
        int res=query(1,1,n,dfn[x],R[x]);
        for(int i = 1, now = fa[x]; i <= 20 && now; i ++, now = fa[now]){
        for(int j = i; j <= 20 ; j ++){
            res += add[j][now] * num[j - i][x];
            // cerr << res << ' ' << f[now][j] << ' ' << num[x][j - 1] << '\n';
            }
        }
        // for(int i=1;i<=20;i++){
        //     x=fa[x];if(!x)break;
        //     res+=num[i][x]*add[i][x];
        // }
        return res;
    }
}tree;

inline void solve(){
    cin>>n>>q;
    for(int i=2;i<=n;i++){int fa;cin>>fa;to[fa].push_back(i);}
    dfs(1,0);
    // tree.build(1,1,n);
    while(q--){
        int op;cin>>op;
        if(op==1){
            int x,y,k;cin>>x>>y>>k;
            tree.modify(x,y,k);
        }
        else {
            int x;cin>>x;
            cout<<tree.query(x)<<"\n";
        }
    }    

}


signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int WTN666=1;//cin>>WTN666;
    while(WTN666--){
        solve();
    }
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3ms
memory: 12160kb

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: