提交记录

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e5 + 5;
int n, fa[MAXN], siz[MAXN], hs[MAXN], ord[MAXN], ordl, q, mxord[MAXN], top[MAXN];
vector<int>son[MAXN];
struct SegmentTree{
    int cnt[MAXN << 2];
    char laz[MAXN << 2]; // 0:inactive, 1:unins, 2:ins
    inline void check_laz(int cur, int lt, int mid, int rt){
        if(laz[cur]){
            laz[cur << 1] = laz[cur];
            laz[cur << 1 | 1] = laz[cur];
            cnt[cur << 1] = (laz[cur] - 1) * (mid - lt + 1);
            cnt[cur << 1 | 1] = (laz[cur] - 1) * (rt - mid);
            laz[cur] = 0;
        }
    }
    int override(int cur, int lt, int rt, int st, int en, char tp){
        if(st <= lt && rt <= en){
            int len = rt - lt + 1;
            int res = tp? len - cnt[cur]: cnt[cur];
            laz[cur] = tp + 1;
            cnt[cur] = tp * len;
            return res;
        }
        int mid = (lt + rt) >> 1;
        check_laz(cur, lt, mid, rt);
        int res = 0;
        if(st <= mid)
            res = override(cur << 1, lt, mid, st, en, tp);
        if(en > mid)
            res += override(cur << 1 | 1, mid + 1, rt, st, en, tp);
        cnt[cur] = cnt[cur << 1] + cnt[cur << 1 | 1];
        return res;
    }
    inline int override(int st, int en, bool tp){return override(1, 0, n - 1, st, en, tp);}
}tree;
void dfs1(int cur){
    siz[cur] = 1;
    hs[cur] = -1;
    if(son[cur].empty())
        return;
    int nn;
    for(int i = 0; i < son[cur].size(); ++i){
        nn = son[cur][i];
        dfs1(nn);
        siz[cur] += siz[nn];
        if(hs[cur] == -1)
            hs[cur] = nn;
        if(siz[hs[cur]] < siz[nn])
            hs[cur] = nn;
    }
}
void dfs2(int cur){
    ord[cur] = ordl++;
    if(hs[cur] != -1){
        top[hs[cur]] = top[cur];
        dfs2(hs[cur]);
        int nn;
        for(int i = 0; i < son[cur].size(); ++i){
            nn = son[cur][i];
            if(nn != hs[cur]){
                top[nn] = nn;
                dfs2(nn);
            }
        }
    }
    mxord[cur] = ordl;
}
int rnode;
char op[15];
inline void ins(int node){
    int ans = 0;
    while(node != -1){
        ans += tree.override(ord[top[node]], ord[node], true);
        node = fa[top[node]];
    }
    cout << ans << endl;
}
inline void unins(int node){cout << tree.override(ord[node], mxord[node], false) << endl; }
int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin >> n;
    /*  Query test
        while(true){int st, en, tp; cin >> st >> en >> tp; cerr << tree.override(st, en, tp) << endl; }*/
    fa[0] = -1;
    for(int i = 1; i < n; ++i){
        cin >> fa[i];
        son[fa[i]].push_back(i);
    }
    dfs1(0);
    dfs2(0);
    /*  Test ord
        cerr << "ORD: "; for(int i = 0; i < n; ++i) cerr << ord[i] << ' '; cerr << endl; */
    cin >> q;
    while(q--){
        cin >> op >> rnode;
        if(op[0] == 'i')
            ins(rnode);
        else
            unins(rnode);
    }
    return 0;
}