1 条题解

  • 0
    @ 2026-1-12 18:00:26

    #include <bits/stdc++.h>
    #define pa p[nd]
    #define root nd[0].c[0]
    #define maxV 256101
    using namespace std;
    
    typedef long long ll;
    
    struct node{
        ll v, s, st, sa, as, m;
        int tag_add, tag_adj;
        int sz, rev, c[2], p;
    }nd[maxV];
    
    int n, q, i;
    int x, y;
    ll z;
    
    inline int dir(int x){return !x[nd].p ? -1 : x == x[nd].pa.c[0] ? 0 : x == x[nd].pa.c[1] ? 1 : -1;}
    
    void reverse(int x){swap(x[nd].c[0], x[nd].c[1]); x[nd].rev ^= 1;}
    
    void adj(int x, ll y){
        if(!x) return;
        x[nd].v = x[nd].m = y;
        x[nd].s = y * x[nd].sz;
        x[nd].tag_adj = y;
        x[nd].tag_add = 0;
        x[nd].sa = x[nd].s + x[nd].st;
    }
    
    void add(int x, ll y){
        if(!x) return;
        x[nd].v += y;
        x[nd].s += y * x[nd].sz;
        x[nd].m += y;
        x[nd].tag_adj ? x[nd].tag_adj += y : x[nd].tag_add += y;
        x[nd].sa = x[nd].s + x[nd].st;
    }
    
    void push_down(int x){
        if(x[nd].rev){
            reverse(x[nd].c[0]); reverse(x[nd].c[1]); x[nd].rev = 0;
        }
        if(x[nd].tag_adj){
            adj(x[nd].c[0], x[nd].tag_adj); adj(x[nd].c[1], x[nd].tag_adj); x[nd].tag_adj = 0;
        }
        if(x[nd].tag_add){
            add(x[nd].c[0], x[nd].tag_add); add(x[nd].c[1], x[nd].tag_add); x[nd].tag_add = 0;
        }
    }
    
    void pull_down(int x){if(~dir(x)) pull_down(x[nd].p); push_down(x);}
    
    inline void up(ll &x, const ll y){x < y ? x = y : 0;}
    
    void update(int x){
        x[nd].s = x[nd].m = x[nd].v;
        x[nd].st = x[nd].as;
        x[nd].sz = 1;
        int lc = x[nd].c[0], rc = x[nd].c[1];
        if(lc){
            x[nd].sz += lc[nd].sz;
            x[nd].s += lc[nd].s;
            up(x[nd].m, lc[nd].m);
            x[nd].st += lc[nd].st;
        }
        if(rc){
            x[nd].sz += rc[nd].sz;
            x[nd].s += rc[nd].s;
            up(x[nd].m, rc[nd].m);
            x[nd].st += rc[nd].st;
        }
        x[nd].sa = x[nd].s + x[nd].st;
    }
    
    void rotate(int x){
        int y = x[nd].p, d = !dir(x);
        nd[y[nd].c[!d] = x[nd].c[d]].p = y;
        x[nd].p = y[nd].p;
        if(~dir(y)) y[nd].pa.c[dir(y)] = x;
        nd[x[nd].c[d] = y].p = x;
        update(y); update(x);
    }
    
    void splay(int x){for(pull_down(x); ~dir(x); rotate(x))
        if(~dir(x[nd].p)) rotate(dir(x) ^ dir(x[nd].p) ? x : x[nd].p);}
    
    void access(int x){
        for(int y = 0; x; y = x, x = x[nd].p){
            splay(x);
            if(x[nd].c[1]) x[nd].as += x[nd].c[1][nd].sa;
            if(x[nd].c[1] = y) x[nd].as -= y[nd].sa;
            update(x);
        }
    }
    
    void make_root(int x){access(x); splay(x); reverse(x);}
    
    int find_root(int x){access(x); splay(x); for(; x[nd].c[0]; x = x[nd].c[0]); return x;}
    
    void link(int x, int y){
        make_root(x); make_root(y);
        x[nd].p = y;
        y[nd].as += x[nd].sa;
        access(x);
    }
    
    void split(int x, int y){make_root(x); access(y); splay(y);}
    
    void cut(int x, int y){split(x, y); x[nd].p = y[nd].c[0] = 0; update(y);}
    
    int main(){
        scanf("%d", &n);
        for(i = 1; i <= n; i++){
            scanf("%lld", &z);
            nd[i].v = nd[i].s = nd[i].m = nd[i].sa = z;
            nd[i].sz = 1;
        }
        for(i = 2; i <= n; i++){
            scanf("%d", &x);
            link(x, i);
        }
        for(scanf("%d", &q); q; --q)
            switch(scanf("%d%d%d", &i, &x, &y), i){
                case 1:{
                    scanf("%lld", &z); split(x, y);
                    add(y, z); break;
                }
                case 2:{
                    scanf("%lld", &z); split(x, y);
                    adj(y, z); break;
                }
                case 3:{
                    split(x, y);
                    printf("%lld\n", nd[y].as + nd[y].v); break;
                }
                case 4:{
                    split(x, y);
                    printf("%lld\n", nd[y].m); break;
                }
                case 5:{
                    split(x, y);
                    printf("%lld\n", nd[y].s); break;
                }
                case 6: link(x, y); break;
                case 7: cut(x, y); break;
            }
        return 0;
    }
    
    
    • 1

    信息

    ID
    6054
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者