Paste: 软件包管理

#include <bits/stdc++.h>
#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<int> 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;
}