思路与算法

依赖关系构成以0号软件包为根的树。安装x要求安装从x到根的所有祖先；卸载x要求卸载x及所有依赖它的后代。

将外部0基编号统一加1，用重链剖分把根路径拆成若干连续区间，并使每个子树对应连续的DFS区间。用支持区间赋值的线段树维护0/1安装状态和每段已安装数量，初始全为0。

安装操作把根路径各段赋为1；一段长度减已安装数就是新装数量。卸载操作把子树区间赋为0，其原已安装数就是卸载数量。在线段树更新的同时返回变化数，累加后输出。

正确性说明

安装所需依赖恰为根到x的祖先路径，且安装后原有包保持安装；把这条路径赋1精确实现题意。卸载x会使所有后代失去依赖，而子树之外的包不依赖x，故仅把该子树赋0精确实现卸载。

重链剖分得到的根路径段互不重叠，子树编号区间也恰含全部后代。区间内原已安装个数由线段树正确维护，赋1的实际变化数为区间长度减原计数，赋0的变化数为原计数。因此每次更新和输出均正确，包括重复安装、重复卸载。

复杂度

n个包、q次操作。依赖图和剖分数组初始化、两遍剖分均O(n)，初始全零线段树数组初始化O(n)。安装需O(log²(n+1))，卸载只更新一个子树区间，需O(log(n+1))。总时间O(n+q log²(n+1))，空间O(n)。

易错点

外部编号从0开始，读入父亲和操作参数时都要一致转换。不能假定父亲编号小于孩子；先建完整无向树再从根遍历。懒标记-1表示无赋值，0表示真实卸载，二者必须区分。安装已安装包和卸载未安装包都可能变化0；卸载根会清空全部状态。n=1也合法。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct HLD {
    int n, tim = 0;
    vector<vector<int>> g;
    vector<int> p, d, sz, heavy, top, id, rev, order;
    HLD(int n)
        : n(n), g(n + 1), p(n + 1), d(n + 1), sz(n + 1, 1), heavy(n + 1), top(n + 1), id(n + 1),
          rev(n + 1) {
        sz[0] = 0;
    }
    void add(int a, int b) {
        g[a].push_back(b);
        g[b].push_back(a);
    }
    void build() {
        order.push_back(1);
        for (int i = 0; i < (int)order.size(); ++i) {
            int u = order[i];
            for (int v : g[u])
                if (v != p[u])
                    p[v] = u, d[v] = d[u] + 1, order.push_back(v);
        }
        for (int i = n - 1; i > 0; --i) {
            int u = order[i], v = p[u];
            sz[v] += sz[u];
            if (sz[u] > sz[heavy[v]])
                heavy[v] = u;
        }
        vector<pair<int, int>> st(1, {1, 1});
        while (!st.empty()) {
            auto q = st.back();
            st.pop_back();
            for (int u = q.first; u; u = heavy[u]) {
                top[u] = q.second;
                id[u] = ++tim;
                rev[tim] = u;
                for (int v : g[u])
                    if (p[v] == u && v != heavy[u])
                        st.push_back({v, v});
            }
        }
    }
};
struct Seg {
    int n;
    vector<int> sum, tag;
    Seg(int n) : n(n), sum(4 * n + 4), tag(4 * n + 4, -1) {
    }
    void put(int k, int l, int r, int v) {
        sum[k] = (r - l + 1) * v;
        tag[k] = v;
    }
    void push(int k, int l, int r) {
        if (tag[k] < 0)
            return;
        int m = (l + r) / 2;
        put(k * 2, l, m, tag[k]);
        put(k * 2 + 1, m + 1, r, tag[k]);
        tag[k] = -1;
    }
    int assign(int k, int l, int r, int a, int b, int v) {
        if (a <= l && r <= b) {
            int changed = v ? r - l + 1 - sum[k] : sum[k];
            put(k, l, r, v);
            return changed;
        }
        push(k, l, r);
        int m = (l + r) / 2, res = 0;
        if (a <= m)
            res += assign(k * 2, l, m, a, b, v);
        if (b > m)
            res += assign(k * 2 + 1, m + 1, r, a, b, v);
        sum[k] = sum[k * 2] + sum[k * 2 + 1];
        return res;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    HLD h(n);
    for (int i = 2, p; i <= n; ++i) {
        cin >> p;
        h.add(i, p + 1);
    }
    h.build();
    Seg st(n);
    int q;
    cin >> q;
    while (q--) {
        string op;
        int x;
        cin >> op >> x;
        ++x;
        int changed = 0;
        if (op == "uninstall")
            changed = st.assign(1, 1, n, h.id[x], h.id[x] + h.sz[x] - 1, 0);
        else {
            while (x) {
                changed += st.assign(1, 1, n, h.id[h.top[x]], h.id[x], 1);
                x = h.p[h.top[x]];
            }
        }
        cout << changed << '\n';
    }
}