同 AcWing 918 软件包管理器
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int, int>;
const int maxn(1e5 + 10);
const int maxm(2e5 + 10);
int ecnt, head[maxn];
int v[maxn], w[maxn];
int fa[maxn], son[maxn], dep[maxn], siz[maxn];
int tim, dfn[maxn], top[maxn];
struct edge {
int to, nxt;
} edges[maxm];
struct node {
int l, r;
int sum, flag;
} tree[maxn << 2];
template<typename T = int>
inline const T read()
{
T x = 0, f = 1;
char ch = getchar();
while (ch < '0' or ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' and ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * f;
}
template<typename T>
inline void write(T x, bool ln)
{
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) write(x / 10, false);
putchar(x % 10 + '0');
if (ln) putchar(10);
}
inline void addEdge(int u, int v)
{
edges[ecnt].to = v;
edges[ecnt].nxt = head[u];
head[u] = ecnt++;
}
inline int ls(int cur)
{
return cur << 1;
}
inline int rs(int cur)
{
return cur << 1 bitor 1;
}
inline void push_up(int cur)
{
tree[cur].sum = tree[ls(cur)].sum + tree[rs(cur)].sum;
}
inline void push_down(int cur)
{
if (compl tree[cur].flag) {
tree[ls(cur)].flag = tree[rs(cur)].flag = tree[cur].flag;
tree[ls(cur)].sum = (tree[ls(cur)].r - tree[ls(cur)].l + 1) * tree[cur].flag;
tree[rs(cur)].sum = (tree[rs(cur)].r - tree[rs(cur)].l + 1) * tree[cur].flag;
tree[cur].flag = -1;
}
}
void build(int cur, int l, int r)
{
tree[cur].l = l;
tree[cur].r = r;
if (l == r) {
tree[cur].sum = w[l];
return;
}
int mid = (l + r) >> 1;
build(ls(cur), l, mid);
build(rs(cur), mid + 1, r);
push_up(cur);
}
void update(int cur, int l, int r, int v)
{
if (tree[cur].l == l and tree[cur].r == r) {
tree[cur].sum = (tree[cur].r - tree[cur].l + 1) * v;
tree[cur].flag = v;
return;
}
push_down(cur);
int mid = (tree[cur].l + tree[cur].r) >> 1;
if (r <= mid) {
update(ls(cur), l, r, v);
} else if (l > mid) {
update(rs(cur), l, r, v);
} else {
update(ls(cur), l, mid, v);
update(rs(cur), mid + 1, r, v);
}
push_up(cur);
}
int query(int cur, int l, int r)
{
if (tree[cur].l == l and tree[cur].r == r) {
return tree[cur].sum;
}
push_down(cur);
int mid = (tree[cur].l + tree[cur].r) >> 1;
if (r <= mid) {
return query(ls(cur), l, r);
}
if (l > mid) {
return query(rs(cur), l, r);
}
return query(ls(cur), l, mid) + query(rs(cur), mid + 1, r);
}
void dfs1(int cur, int pre)
{
fa[cur] = pre;
dep[cur] = dep[pre] + 1;
siz[cur] = 1;
int maxsize = -1;
for (int i = head[cur]; compl i; i = edges[i].nxt) {
int nxt = edges[i].to;
if (nxt == pre) continue;
dfs1(nxt, cur);
siz[cur] += siz[nxt];
if (maxsize < siz[nxt]) {
maxsize = siz[nxt];
son[cur] = nxt;
}
}
}
void dfs2(int cur, int tp) {
dfn[cur] = ++tim;
w[tim] = v[cur];
top[cur] = tp;
if (not son[cur]) return;
dfs2(son[cur], tp);
for (int i = head[cur]; compl i; i = edges[i].nxt) {
int nxt = edges[i].to;
if (nxt not_eq son[cur] and nxt not_eq fa[cur]) {
dfs2(nxt, nxt);
}
}
}
void update_chain(int u, int v, int val)
{
while (top[u] not_eq top[v]) {
if (dep[top[u]] < dep[top[v]]) {
swap(u, v);
}
update(1, dfn[top[u]], dfn[u], val);
u = fa[top[u]];
}
if (dep[u] > dep[v]) {
swap(u, v);
}
update(1, dfn[u], dfn[v], val);
}
inline void update_son(int cur, int val)
{
update(1, dfn[cur], dfn[cur] + siz[cur] - 1, val);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
memset(head, -1, sizeof head);
int n = read();
for (int u = 2; u <= n; ++u) {
int v = read() + 1;
addEdge(u, v);
addEdge(v, u);
}
dfs1(1, 1);
dfs2(1, 1);
build(1, 1, n);
int q = read();
while (q--) {
char op[10];
scanf("%s", op);
int x = read() + 1;
int pre = tree[1].sum;
if (*op == 'i') {
update_chain(1, x, 1);
write(tree[1].sum - pre, true);
} else {
update_son(x, 0);
write(pre - tree[1].sum, true);
}
}
return 0;
}