Submission #1339968

#TimeUsernameProblemLanguageResultExecution timeMemory
1339968AndreyMigration Plan (JOI25_migration)C++20
100 / 100
4687 ms1781820 KiB
#include<bits/stdc++.h>
using namespace std;

struct node {
    int sb = 0;
    int nl = -1;
    int nr = -1;
};

node red;
vector<node> seg[2000001];
vector<pair<int,int>> wut[2000001];
vector<int> haha[2000001];
vector<int> bruh(2000001);

void upd(int l, int r, int p, int c, int x, int y) {
    if(l == r) {
        seg[y][x].sb = seg[y][x].sb+c;
        return;
    }
    int mid = (l+r)/2;
    if(p <= mid) {
        if(seg[y][x].nl == -1) {
            seg[y][x].nl = seg[y].size();
            seg[y].push_back(red);
        }
        upd(l,mid,p,c,seg[y][x].nl,y);
    }
    else {
        if(seg[y][x].nr == -1) {
            seg[y][x].nr = seg[y].size();
            seg[y].push_back(red);
        }
        upd(mid+1,r,p,c,seg[y][x].nr,y);
    }
    int z = 0;
    if(seg[y][x].nl != -1) {
        z+=seg[y][seg[y][x].nl].sb;
    }
    if(seg[y][x].nr != -1) {
        z+=seg[y][seg[y][x].nr].sb;
    }
    seg[y][x].sb = z;
}

int calc(int l, int r, int ql, int qr, int x, int y) {
    if(x == -1) {
        return 0;
    }
    if(ql == l && qr == r) {
        return seg[y][x].sb;
    }
    int mid = (l+r)/2;
    if(qr <= mid) {
        return calc(l,mid,ql,qr,seg[y][x].nl,y);
    }
    else if(ql > mid) {
        return calc(mid+1,r,ql,qr,seg[y][x].nr,y);
    }
    else {
        return calc(l,mid,ql,mid,seg[y][x].nl,y)+calc(mid+1,r,mid+1,qr,seg[y][x].nr,y);
    }
}

int n,p = 0;
vector<int> pos(2000001);
vector<int> st(2000001);
vector<int> dep(2000001);

void dfs(int a, int d) {
    dep[a] = d;
    p++;
    pos[a] = p;
    upd(1,n,p,bruh[a],0,d);
    wut[d].push_back({p,bruh[a]});
    st[a] = 1;
    for(int v: haha[a]) {
        dfs(v,d+1);
        st[a]+=st[v];
    }
}

void dude(int a, int b) {
    if(wut[a].size() < wut[b].size()) {
        swap(wut[a],wut[b]);
        swap(seg[a],seg[b]);
    }
    for(int i = 0; i < wut[b].size(); i++) {
        upd(1,n,wut[b][i].first,wut[b][i].second,0,a);
        wut[a].push_back(wut[b][i]);
    }
    wut[b].clear();
    seg[b].clear();
    seg[b].push_back(red);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    red.nl = -1;
    red.nr = -1;
    red.sb = 0;
    cin >> n;
    int a;
    for(int i = 0; i < n; i++) {
        seg[i].push_back(red);
    }
    for(int i = 2; i <= n; i++) {
        cin >> a;
        haha[a].push_back(i);
    }
    for(int i = 1; i <= n; i++) {
        cin >> bruh[i];
    }
    dfs(1,0);
    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if(t == 1) {
            int x,y;
            cin >> x >> y;
            dude(y,x);
        }
        else if(t == 2) {
            int a,b;
            cin >> a >> b;
            upd(1,n,pos[a],b,0,dep[a]);
            wut[dep[a]].push_back({pos[a],b});
        }
        else {
            int a;
            cin >> a;
            cout << calc(1,n,pos[a],pos[a]+st[a]-1,0,dep[a]) << "\n";
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...