QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134036#4941. Tree Beautywtn135687WA 74ms79584kbC++146.4kb2023-08-02 20:54:562023-08-02 20:55:03

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 20:55:03]
  • 评测
  • 测评结果:WA
  • 用时:74ms
  • 内存:79584kb
  • [2023-08-02 20:54:56]
  • 提交

answer

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

const int N = 1e6+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];
    // void build(int id,int l,int r){
    //     if(l==r){seg[id].len=1;return ;}
    //     int mid=l+r>>1;
    //     build(id<<1,l,mid);
    //     build(id<<1|1,mid+1,r);
    //     seg[id].len=seg[id<<1].len+seg[id<<1|1].len;
    // }
    // void setTag(int id,int t){
    //     seg[id].sum+=seg[id].len*t;
    //     seg[id].t+=t;
    //     // cerr<<"setTag:  id="<<id<<" sum="<<seg[id].sum<<" t="<<t<<" len="<<seg[id].len<<"\n";
    // }
    // void pushDown(int id){
    //     int t=seg[id].t;
    //     seg[id<<1].sum+=seg[id<<1].len*t;seg[id<<1|1].sum+=seg[id<<1|1].len*t;
    //     seg[id<<1].t+=t;seg[id<<1|1].t+=t;
    //     seg[id].t=0;
    // }
    // void upDate(int id){
    //     seg[id].sum=seg[id<<1].sum+seg[id<<1|1].sum;
    //     // cerr<<"update id="<<id<<" sum="<<seg[id].sum<<"\n";
    // }
    // void modify(int id,int l,int r,int ql,int qr,int t){
    //     // cerr<<"add "<<id<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<t<<"\n";
    //     if(!(l<=ql&&qr<=r))return ;
    //     if(l==ql&&r==qr){
    //         setTag(id,t);return ;
    //     }
    //     pushDown(id);
    //     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){
    //     // cerr<<"query tree"<<ql<<" "<<qr<<"\n";
    //     // cerr<<seg[id].sum<<"!\n";
    //     if(l==qr&&r==qr)return seg[id].sum;
    //     pushDown(id);
    //     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],dfn[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: 1ms
memory: 50728kb

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: 1ms
memory: 36244kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 74ms
memory: 79584kb

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:

0
0
0
76417
0
129963
0
76417
0
0
78607
78607
468817
453762
230471
144023
230470
230470
230470
22826477
11376799
0
144023
230470
5811920
78063
745421
305459
242814
474024
745421
13938831
833215
833215
1072013
476935
833215
493756
230507
7366190
393253
0
256058
750988
528845
393254
232881
1172104
2846...

result:

wrong answer 1st lines differ - expected: '1818724600', found: '0'