QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134051#4941. Tree Beautywtn135687TL 3ms19948kbC++145.9kb2023-08-02 21:16:532023-08-02 21:16:55

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:16:55]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:19948kb
  • [2023-08-02 21:16:53]
  • 提交

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&&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,  val,l, r);
            return ;
        }
        int mid = (l + r) >> 1;
        pushDown(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].sum = seg[id << 1].sum + seg[id << 1 | 1].sum;
    }
    // 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: 0ms
memory: 19948kb

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: 12868kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Time Limit Exceeded

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:

1818724600
1818724600
1818724600
672469600
2920352548
1987509504
2920352548
2782801948
2920352548
2920352548
7518672977
11295020015
7543062544
4383229800
19258702398
22947288874
15221147536
15428570536
14322314536
9119623396
12969783379
26872020588
25039643385
22398749036
27923029652
31534374661
745...

result: