decomposition, C++ (gcc)

Language: Layout:

//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
    //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long int ll;
#define pii pair<ll, ll>

struct node{
    int val, ind;

node() : val(-1e6), ind(-1e6){}
    node(int v, int i) : val(v), ind(i){}

bool operator < (const node& rhs) const{
        if(val == rhs.val) return ind > rhs.ind;
        return val > rhs.val;
    }

bool operator == (const node& rhs) const{
        return (rhs.val == val && ind == rhs.ind);
    }
};

int mapIt[28][200001];

struct seg_tree{
    node *seg;
    int n;
    
    seg_tree(int x, const vector<node>& v) : n(x-1){
        seg = new node[4*n+1];
        build(0, n, 0, v);
    }
    
    void build(int l, int r, int i, const vector<node>& v){
        if(l == r){
            seg[i] = v[l];
            return;
        }
        int mid = (l+r)/2;
        build(l, mid, i*2+1, v);
        build(mid+1, r, i*2+2, v);
        seg[i] = min(seg[i*2+1], seg[i*2+2]);
    }
    
    void update(int l, int r, int i, int pos, const node& v){
        if(l == r){
            seg[i] = v;
            return;
        }
        int mid = (l+r)/2;
        if(mid >= pos) update(l, mid, i*2+1, pos, v);
        else update(mid+1, r, i*2+2, pos, v);
        seg[i] = min(seg[i*2+1], seg[i*2+2]);
    }
    
    void update(int p, const node& v){
        update(0, n, 0, p, v);
    }
    
    node query(int l, int r, int i, int x, int y){
        if(r < x || l > y) return node();
        if(l >= x && r <= y) return seg[i];
        int mid = (l+r)/2;
        return min(query(l, mid, i*2+1, x, y), query(mid+1, r, i*2+2, x, y));
    }
    
    node query(int l, int r){
        return query(0, n, 0, l, r);
    }
    
    void print(){
        for(int j = 0; j <= n; j++){
            node cur = query(0, n, 0, j, j);
            cout << "(" << cur.val << " " << cur.ind << ")  ";
        }
        cout << endl;
    }
};

struct node2{
    multiset<node> v;

void add(node t){
        v.insert(t);
    }
    void rmv(node t){
        v.erase(v.find(t));
    }
};

set<int> g[200001];

int n = 0, level[200001] = {0}, dp[28][200001], root, sub[200001], color[200001] = {0};

int dist[28][200001], lvl2[200001], par2[200001], parBranch[200001], sub2[200001] = {0}, st[200001], ed[200001];

vector<int> below[200001];

seg_tree *agg[200001];

int dfs(int src, int par){
    level[src] = level[par] + 1;
    dp[0][src] = par;
    for(int j = 1; j < 28; j++)
        dp[j][src] = dp[j-1][dp[j-1][src]];

sub[src] = 1;
    for(auto it : g[src])
        if(it != par) sub[src] += dfs(it, src);
    return sub[src];
}

int dfsCentroid(int src, int par, int up, int tot){
    for(auto it : g[src])
        if(it != par && sub[it] > (tot/2)) return dfsCentroid(it, src, tot - sub[it], tot);
    return src;
}

int dfsArrange(int src, int par){
    sub[src] = 1;
    for(auto it : g[src])
        if(it != par) sub[src] += dfsArrange(it, src);
    return sub[src];
}

void decompose(int src){
    const set<int> t = g[src];
    for(auto it : t){
        g[src].erase(it);
        g[it].erase(src);

int centroid = dfsCentroid(it, src, 0, sub[it]);
        g[src].insert(centroid);
        dfsArrange(centroid, src);

decompose(centroid);
    }
}

int LCA(int u, int v){
    if(level[u] > level[v]) swap(u, v);
    int dif = level[v] - level[u];
    for(int j = 27; j >= 0; j--)
        if(dif >= (1 << j)){
            dif -= (1 << j);
            v = dp[j][v];
        }
    if(u == v) return u;

for(int j = 27; j >= 0; j--)
        if(dp[j][v] != dp[j][u]) u = dp[j][u], v = dp[j][v];
    return dp[0][v];
}

int calcDist(int u, int v){
    int lca = LCA(u, v);
    return (level[u] + level[v] - 2*level[lca]);
}

void dfsLast(int src, int par){
    below[src].pb(src);
    par2[src] = par;
    sub2[src] = 1;
    lvl2[src] = lvl2[par] + 1;
    dist[lvl2[src]][src] = 0;

int ind = 1;
    for(auto it : g[src]){
        int cur = src;
        while(cur != 0){
            dist[lvl2[cur]][it] = calcDist(it, cur);
            cur = par2[cur];
        }
        dfsLast(it, src);
        for(auto i : below[it])
            below[src].pb(i);
        
        st[it] = ind;
        ed[it] = ind + sub2[it] - 1;
        ind += sub2[it];
        sub2[src] += sub2[it];
    }
    
    vector<node> v;
    for(int j = 0; j < (int)below[src].size(); j++){
        //cout << src << " " << below[src][j] << endl;
        mapIt[lvl2[src]][below[src][j]] = j;
        v.pb(node(dist[lvl2[src]][below[src][j]], below[src][j]));
    }
    agg[src] = new seg_tree(below[src].size(), v);
}

void print(int src, int par){
    cout << src << " " << par << endl;
    for(auto it : g[src])
        print(it, src);
}

void decomposeTree(){
    dfs(1, 0);
    root = dfsCentroid(1, 0, 0, n);
    dfs(root, 0);
    decompose(root);
    //print(root, 0);
    dfsLast(root, 0);
}

void add(int src){
    int cur = src, dis = 0, branch = 0;
    while(cur != 0){
        agg[cur] -> update(mapIt[lvl2[cur]][src], node(dis, src));
        cur = par2[cur];
        dis = dist[lvl2[cur]][src];
    }
}

void rmv(int src){
    int cur = src, dis = 0, branch = 0;
    while(cur != 0){
        agg[cur] -> update(mapIt[lvl2[cur]][src], node(-1e6, -1e6));
        cur = par2[cur];
        dis = dist[lvl2[cur]][src];
    }
}

void print(multiset<node> m){
    for(auto it : m)
        cout << "(" << it.val << " " << it.ind << ")  ";
    cout << endl;
}

void print(){
    cout << "\n\nagg : \n";
    for(int i = 1; i <= n; i++)
        agg[i] -> print();
}

int query(int src){
    int cur = src, l = n+1, r = n+1, dis = 0;
    node ans;
    while(cur != 0){
        int lft = 0, rgt = sub2[cur] - 1;
        node t;
        if(l > 0){
            t = agg[cur] -> query(lft, l-1);
            t.val += dis;
            ans = min(ans, t);
        }
        if(r+1 <= rgt){
            t = agg[cur] -> query(r+1, rgt);
            t.val += dis;
            ans = min(ans, t);
        }
        l = st[cur];
        r = ed[cur];
        cur = par2[cur];
        dis = dist[lvl2[cur]][src];
    }
    return ans.ind;
}

void initialize(){
    for(int j = 0; j <= n; j++){
        agg[j] = NULL;
        //info[j].clear();
        below[j].clear();
        g[j].clear();
        level[j] = 0;
        lvl2[j] = 0;
        color[j] = 0;
    }
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

int t;
    scanf("%d",&t);
    while(t--){
        initialize();
        int m = 200000;
        n = 200000;
        scanf("%d %d",&n ,&m);
        for(int j = 2; j <= n; j++){
            int x = j-1;
            scanf("%d",&x);
            g[x].insert(j);
            g[j].insert(x);
        }
        decomposeTree();
        //print();
        while(m--){
            int x = (m * 2 + 100*3) % n, fg = 1;
            if(x == 0) x = m;
            scanf("%d",&x);
            if(color[x]) add(x), fg = 0;
            printf("%d\n",query(x));
            if(fg) rmv(x);
            color[x] ^= 1;
            //print();
        }
    }
    return 0;
}

Show compiler warnings [ + ] Compiler args [ - ] Show input
Compilation time: 4.16 sec, absolute running time: 0.26 sec, cpu time: 0.14 sec, memory peak: 15 Mb, absolute service time: 4,43 sec