#include #define segmid ((l + r) >> 1) using namespace std; const int maxn = 400005; int fa[maxn], dep[maxn], top[maxn], size[maxn], son[maxn], id[maxn], rnk[maxn], cnt; int ins[maxn]; vector e[maxn]; int n, q; namespace segtree { int segins[maxn]; void build(int l, int r, int rt) { if (l == r) { segins[rt] = 0; return; } build(l, segmid, rt * 2); build(segmid + 1, r, rt * 2 + 1); segins[rt] = 0; } void change(int l, int r, int x, bool val, int rt) { if (l == r) { segins[rt] = val; return; } if (x <= segmid) { change(l, segmid, x, val, rt * 2); } else { change(segmid + 1, r, x, val, rt * 2 + 1); } segins[rt] = segins[rt * 2] + segins[rt * 2 + 1]; } int getSum(int l, int r, int u, int v, int rt) { if (u > v) swap(u, v); if (l == r) { return segins[rt]; } if (u > segmid) { // ??? return getSum(segmid + 1, r, u, v, rt * 2 + 1); } else if (v <= segmid) { // ??? return getSum(l, segmid, u, v, rt * 2); } else { return getSum(l, segmid, u, segmid, rt * 2) + getSum(segmid + 1, r, segmid + 1, v, rt * 2 + 1); } } } // namespace segtree void dfs1(int x, int fat) { fa[x] = fat; dep[x] = dep[fat] + 1; size[x] = 1; for (int i = 0; i < e[x].size(); i++) { int z = e[x][i]; if (z == fat) continue; dfs1(z, x); size[x] += size[z]; if (size[z] > size[son[x]]) son[x] = z; } } void dfs2(int x, int topz) { top[x] = topz; id[x] = ++cnt; rnk[cnt] = x; if (son[x] == 0) return; dfs2(son[x], topz); for (int i = 0; i < e[x].size(); i++) { int z = e[x][i]; if (z == fa[x]) continue; if (son[x] != z) { dfs2(z, z); } } } void treeUpdate(int u, int t) { segtree::change(1, n, id[u], t, 1); } int treeQnodeCnt; int treeNodeCnt(int x, int y) { if (id[x] > id[y]) return id[x] - id[y] + 1; else return id[y] - id[x] + 1; } int treeQsum(int u, int v) { treeQnodeCnt = 0; int ans = 0; while (top[u] != top[v]) { // Chain Jump if (dep[top[u]] < dep[top[v]]) swap(u, v); ans += segtree::getSum(1, n, id[top[u]], id[u], 1); treeQnodeCnt += treeNodeCnt(top[u], u); u = fa[top[u]]; } treeQnodeCnt += treeNodeCnt(u, v); return ans + segtree::getSum(1, n, id[u], id[v], 1); } void treeInstall(int u, int v) { int temp1, temp2; while (top[u] != top[v]) { // Chain Jump if (dep[top[u]] < dep[top[v]]) swap(u, v); temp1 = id[u]; temp2 = id[top[u]]; if (temp1 > temp2) swap(temp1, temp2); for (int i = temp1; i <= temp2; i++) { segtree::change(1, n, i, 1, 1); } u = fa[top[u]]; } temp1 = id[u]; temp2 = id[v]; if (temp1 > temp2) swap(temp1, temp2); for (int i = temp1; i <= temp2; i++) { segtree::change(1, n, i, 1, 1); } } int treeUninstall(int x) { int summ = 0; segtree::change(1, n, id[x], 0, 1); summ++; // cout << "LOG uninstalled (" << x - 1 << ")" << endl; for (int i = 0; i < e[x].size(); i++) { int z = e[x][i]; if (z == fa[x] || !segtree::getSum(1, n, id[z], id[z], 1)) continue; summ += treeUninstall(z); } return summ; } int main() { ios::sync_with_stdio(false); cin.tie(0); { // ?????? cin >> n; for (int i = 2; i <= n; i++) { int a; cin >> a; e[i].push_back(a + 1); e[a + 1].push_back(i); } memset(segtree::segins, 0, maxn); } // ?????? n++; { // ???? dfs1(1, 0); // cout << "[debug] dfs1 done" << endl; dfs2(1, 1); // cout << "[debug] dfs2 done" << endl; segtree::build(1, n, 1); // for (int i = 1; i <= n; i++) { // cout << "SEGTREE info: " << segtree::getMax(1, n, i, i, 1) // << endl; // } } // ???? { // ?? cin >> q; while (q--) { string op; int u; cin >> op >> u; if (op == "install") { if (segtree::getSum(1, n, id[u + 1], id[u + 1], 1)) { cout << 0 << '\n'; continue; } int sum = treeQsum(1, u + 1); cout << treeQnodeCnt - sum << '\n'; // treeUpdate(u + 1, 1); treeInstall(1, u + 1); } else { if (!segtree::getSum(1, n, id[u + 1], id[u + 1], 1)) { cout << 0 << '\n'; continue; } // op == "uninstall" cout << treeUninstall(u + 1) << '\n'; } } } // ?? return 0; }