Submission #1340562

#TimeUsernameProblemLanguageResultExecution timeMemory
1340562vladiliusMigration Plan (JOI25_migration)C++20
100 / 100
3857 ms814548 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>

struct FT{
    vector<int> bit;
    int n;
    FT(int ns){
        n = ns;
        bit.resize(n + 1);
    }
    void upd(int x, int y){
        while (x <= n){
            bit[x] += y;
            x |= (x + 1);
        }
    }
    int get(int v){
        int out = 0;
        while (v > 0){
            out += bit[v];
            v = (v & (v + 1)) - 1;
        }
        return out;
    }
    int get(int l, int r){
        return get(r) - get(l - 1);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> g[n + 1];
    for (int i = 2; i <= n; i++){
        int p; cin>>p;
        g[p].pb(i);
    }
    
    vector<int> d(n + 1), tin(n + 1), tout(n + 1);
    int timer = 0;
    function<void(int)> dfs = [&](int v){
        tin[v] = ++timer;
        for (int i: g[v]){
            d[i] = d[v] + 1;
            dfs(i);
        }
        tout[v] = timer;
    };
    dfs(1);
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i];
    }
    
    vector<int> v[n + 1];
    vector<vector<int>> G = {{}};
    for (int i = 0; i < n; i++){
        v[i].pb(i + 1);
        G.pb({});
    }
    int cc = n;
    
    vector<pii> qs[n + 1], upd[n + 1];
    for (int i = 1; i <= n; i++){
        upd[tin[i]].pb({v[d[i]].back(), a[i]});
    }

    int q; cin>>q;
    vector<int> out(q + 1, -1);
    for (int i = 1; i <= q; i++){
        int type, x; cin>>type>>x;
        if (type == 1){
            int y; cin>>y;
            v[x].pb(++cc); G.pb({});
            v[y].pb(++cc); G.pb({});
            
            G[cc].pb(v[y][v[y].size() - 2]);
            G[cc].pb(v[x][v[x].size() - 2]);
        }
        else if (type == 2){
            int y; cin>>y;
            v[d[x]].pb(++cc); G.pb({});
            G[cc].pb(v[d[x]][v[d[x]].size() - 2]);
            upd[tin[x]].pb({cc, y});
        }
        else {
            qs[tout[x]].pb({v[d[x]].back(), i});
            qs[tin[x] - 1].pb({v[d[x]].back(), -i});
            out[i] = 0;
        }
    }
    
    vector<int> ti(cc + 1), to(cc + 1);
    timer = 0;
    function<void(int)> fill = [&](int v){
        ti[v] = ++timer;
        for (int i: G[v]){
            fill(i);
        }
        to[v] = timer;
    };
    for (int i = cc; i > 0; i--){
        if (!ti[i]){
            fill(i);
        }
    }

    FT T(cc);
    for (int i = 1; i <= n; i++){
        for (auto [x, y]: upd[i]){
            T.upd(ti[x], y);
        }
        for (auto [x, ii]: qs[i]){
            if (ii < 0){
                ii = -ii;
                out[ii] -= T.get(ti[x], to[x]);
            }
            else {
                out[ii] += T.get(ti[x], to[x]);
            }
        }
    }
    
    for (int i = 1; i <= q; i++){
        if (out[i] != -1){
            cout<<out[i]<<"\n";
        }
    }
}
#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...