• 安装软件：root~x 的 0 都变成 1
• 卸载软件：x 的子树的 1 都变成 0（x 子树的 dfs 序为 dfn[x]~dfn[x]+siz[x]-1）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
const int INF = 0x3f3f3f3f;
int n, q;
vector<int> e[MAXN];
int w[MAXN]; // 每个点的权值
//---------树剖基础---------
// 每个点的：父节点、深度、大小、重子节点
int fa[MAXN], dep[MAXN], siz[MAXN], hson[MAXN];
void dfs_build(int u, int fat)
{
    hson[u] = 0;
    siz[hson[u]] = 0;
    siz[u] = 1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fat)
            continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs_build(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[hson[u]])
            hson[u] = v;
    }
}
// 每个点的：所在链的链顶、重边优先的 dfs 序、dfs序对应的节点编号
int tot, top[MAXN], dfn[MAXN], rnk[MAXN];
void dfs_div(int u, int fa)
{
    dfn[u] = ++tot;
    rnk[tot] = u;
    if (hson[u])
    {
        top[hson[u]] = top[u];
        dfs_div(hson[u], u);
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            if (v == fa || v == hson[u])
                continue;
            top[v] = v;
            dfs_div(v, u);
        }
    }
}

//---------线段树---------
struct SegTree
{
    int sum[MAXN * 4], lazy[MAXN * 4];
    void build(int o, int l, int r)
    {
        if (l == r)
        {
            sum[o] = w[rnk[l]];
            lazy[o] = -1;
            return;
        }
        int mid = (l + r) >> 1;
        build(o * 2, l, mid);
        build(o * 2 + 1, mid + 1, r);
        sum[o] = sum[o * 2] + sum[o * 2 + 1];
    }
    int query_sum(int o, int l, int r, int ql, int qr)
    {
        if (l > qr || r < ql)
            return 0;
        if (ql <= l && r <= qr)
            return sum[o];
        int mid = (l + r) >> 1;
        // 下放懒标记
        if (lazy[o] >= 0)
        {
            sum[o * 2] = lazy[o] * (mid - l + 1);
            sum[o * 2 + 1] = lazy[o] * (r - mid);
            lazy[o * 2] = lazy[o];
            lazy[o * 2 + 1] = lazy[o];
            lazy[o] = -1;
        }
        return query_sum(o * 2, l, mid, ql, qr) + query_sum(o * 2 + 1, mid + 1, r, ql, qr);
    }
    // 把[x,y]区间设置为k(>=0)
    void update(int now, int l, int r, int x, int y, int k)
    {
        if (x <= l && r <= y)
        {
            sum[now] = k * (r - l + 1);
            lazy[now] = k;
            return;
        }
        int mid = (l + r) / 2;
        // 下放懒标记
        if (lazy[now] >= 0)
        {
            sum[now * 2] = lazy[now] * (mid - l + 1);
            sum[now * 2 + 1] = lazy[now] * (r - mid);
            lazy[now * 2] = lazy[now];
            lazy[now * 2 + 1] = lazy[now];
            lazy[now] = -1;
        }
        if (x <= mid)
            update(now * 2, l, mid, x, y, k);
        if (y > mid)
            update(now * 2 + 1, mid + 1, r, x, y, k);
        sum[now] = sum[now * 2] + sum[now * 2 + 1];
    }
} st;
//---------操作---------
int install(int x)
{
    int res = 0;
    while (top[x] != 1)
    {
        // 0->1
        res += (dfn[x] - dfn[top[x]] + 1) - st.query_sum(1, 1, n, dfn[top[x]], dfn[x]);
        st.update(1, 1, n, dfn[top[x]], dfn[x], 1);
        x = fa[top[x]];
    }
    res += dfn[x] - st.query_sum(1, 1, n, 1, dfn[x]);
    st.update(1, 1, n, dfn[1], dfn[x], 1);
    return res;
}
int uninstall(int x)
{
    int res = st.query_sum(1, 1, n, dfn[x], dfn[x] + siz[x] - 1);
    st.update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, 0);
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        int fa;
        cin >> fa;
        fa++;
        e[fa].push_back(i);
    }
    // w[i]: i 号软件是否被安装了
    for (int i = 1; i <= n; i++)
        w[i] = 0;
    w[1] = 0;
    dep[1] = 1;
    fa[1] = 0;
    dfs_build(1, 0);
    tot = 0;
    top[1] = 1;
    dfs_div(1, 0);
    st.build(1, 1, n);
    cin >> q;
    while (q--)
    {
        string op;
        int x;
        cin >> op >> x;
        x++;
        if (op == "install")
        {
            cout << install(x) << endl;
        }
        if (op == "uninstall")
        {
            cout << uninstall(x) << endl;
        }
    }
    return 0;
}