Submission #1340262

#TimeUsernameProblemLanguageResultExecution timeMemory
1340262alexddMigration Plan (JOI25_migration)C++20
100 / 100
3978 ms620880 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXV = 4e6 + 5;
const int MAXN = 2e6 + 5;
int val[MAXV];
int tin[MAXV], tout[MAXV], depth[MAXV];

/*int anc[MAXN][21];
int myanc(int x, int d)
{
    for(int b=0;b<21;b++)
        if((1<<b)&d)
            x = anc[x][b];
    return x;
}*/

struct GROUP
{
    map<int,int> fr;
    void init(vector<int> nodes)
    {
        for(int x:nodes)
            fr[tin[x]] += val[x];
    }
    void reset()
    {
        fr.clear();
    }
};
GROUP comp[MAXN];

void merge(int idx, int idy)
{
    assert(idx < idy);
    if(comp[idx].fr.size() < comp[idy].fr.size())
    {
        swap(comp[idx], comp[idy]);
    }
    for(auto it:comp[idy].fr)
    {
        if(it.second)
            comp[idx].fr[it.first] += it.second;
    }
    comp[idy].reset();
}
int query(int id, int le, int ri)
{
    auto it = comp[id].fr.lower_bound(le);
    int sum = 0;
    while(it != comp[id].fr.end() && (*it).first <= ri)
    {
        sum = sum + (*it).second;
        it = comp[id].fr.erase(it);
    }
    if(sum) comp[id].fr[le] += sum;
    return sum;
}

int n, timer;
int parent[MAXN];
vector<int> con[MAXN];
vector<int> ofdepth[MAXN];
void dfs(int nod)
{
    tin[nod] = ++timer;
    for(int adj:con[nod])
    {
        depth[adj] = depth[nod] + 1;
        dfs(adj);
    }
    tout[nod] = timer;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        cin>>parent[i];
        con[parent[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)
        cin>>val[i];
    dfs(1);
    for(int i=1;i<=n;i++)
        ofdepth[depth[i]].push_back(i);
    for(int d=0;d<n;d++)
    {
        comp[d].init(ofdepth[d]);
    }
    int q;
    cin>>q;
    while(q--)
    {
        int tip;
        cin>>tip;
        if(tip == 1)
        {
            int x,y;
            cin>>x>>y;
            swap(x, y);
            assert(x < y);
            merge(x, y);
        }
        else if(tip == 2)
        {
            int a, newv;
            cin>>a>>newv;
            comp[depth[a]].fr[tin[a]] += newv;
        }
        else
        {
            assert(tip == 3);
            int b;
            cin>>b;
            cout<<query(depth[b], tin[b], tout[b])<<"\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...