P2146 [NOI2015] 软件包管理器 树链剖分

//题目大意：给定一棵树，树上的每个节点是一个软件，现在给出如下两个指令，install与uninstall，
//          如果需要install x号软件，那么我需要安装他到根节点之间的所有软件；如果我需要卸载
//          uninstall所有的软件，那么我需要先卸载他子树中的所有软件。现在我们询问每次给定操作
//          对其他多少软件造成了影响
// 
// 思路：install很简单，直接处理该点到根节点之间的链即可
//       uninstall直接处理l[x]到r[x]这个子树区间就好，因为他们在dfs序中是连续的
//
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> mp[N];
int n, m;
int l[N], r[N], idx[N];
int sz[N], hs[N], tot, top[N], dep[N], fa[N];
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
void dfs1(int u, int f) {//第一遍dfs,求子树大小，重儿子，父亲，深度
    sz[u] = 1;
    hs[u] = -1;
    fa[u] = f;
    dep[u] = dep[f] + 1;
    for (auto v : mp[u]) {
        if (v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (hs[u] == -1 || sz[v] > sz[hs[u]])
            hs[u] = v;
    }
}
void dfs2(int u, int t) {//第二次dfs,求每个点的dfs序，重链上的链头元素
    top[u] = t;
    l[u] = ++tot;
    idx[tot] = u;
    if (hs[u] != -1) {
        dfs2(hs[u], t);
    }//优先遍历重链，如此一来将重链的dfs序搞成连续的
    for (auto v : mp[u]) {
        if (v != fa[u] && v != hs[u])
            dfs2(v, v);//这里很重要，最开始被dls坑了
    }
    r[u] = tot;
}
struct info {
    int st;//区间未安装
    int fst;//-1全卸载，0无标记，1全安装
}seg[4 * N];
void update(int id) {
    seg[id].st = seg[2 * id].st + seg[2 * id + 1].st;
}
void build(int id, int l, int r) {
    if (l == r) {
        //我们是对dfs序建树，所以这里要注意是dfs序中l号点
        seg[id].st = 1;
        seg[id].fst = 0;
    }
    else {
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        update(id);
    }
}
void pushdown(int id, int l, int r) {
    if (seg[id].fst == 0) return;
    int mid = (l + r) / 2;
    if (seg[id].fst == 1) {
        seg[id * 2].st = (mid - l + 1);
        seg[id * 2 + 1].st = (r - mid);
        seg[id * 2].fst = seg[2 * id + 1].fst = 1;
        seg[id].fst = 0;
    }
    else {
        seg[id * 2].st = 0;//全部变为安装
        seg[id * 2 + 1].st = 0;
        seg[id * 2].fst = seg[2 * id + 1].fst = -1;
        seg[id].fst = 0;
    }
}
int query1(int id, int l, int r, int ql, int qr) {
    if (ql == l && qr == r) {
        return seg[id].st;
    }
    pushdown(id, l, r);
    int mid = (l + r) / 2;
    if (qr <= mid) return query1(id * 2, l, mid, ql, qr);
    else if (ql > mid) return query1(id * 2 + 1, mid + 1, r, ql, qr);
    else {
        return query1(id * 2, l, mid, ql, mid) + query1(id * 2 + 1, mid + 1, r, mid + 1, qr);
    }
}
int query2(int id, int l, int r, int ql, int qr) {
    if (ql == l && qr == r) {
        return (r - l + 1) - seg[id].st;//已经被安装的软件数目
    }
    pushdown(id, l, r);
    int mid = (l + r) / 2;
    if (qr <= mid) return query2(id * 2, l, mid, ql, qr);
    else if (ql > mid) return query2(id * 2 + 1, mid + 1, r, ql, qr);
    else {
        return query2(id * 2, l, mid, ql, mid) + query2(id * 2 + 1, mid + 1, r, mid + 1, qr);
    }
}
void modify(int id, int l, int r, int ql, int qr, int od) {
    if (ql == l && qr == r) {
        if (od == -1) {
            seg[id].st = 0; seg[id].fst = -1;
            return;
        }
        else {
            seg[id].st = (r - l + 1); seg[id].fst = 1;
            return;
        }
    }
    pushdown(id, l, r);
    int mid = (l + r) / 2;
    if (qr <= mid) modify(2 * id, l, mid, ql, qr, od);
    else if (ql > mid) modify(2 * id + 1, mid + 1, r, ql, qr, od);
    else {
        modify(id * 2, l, mid, ql, mid, od); 
        modify(id * 2 + 1, mid + 1, r, mid + 1, qr, od);
    }
    update(id);
}
int query(int x, int od) {
    int ans = 0;
    if (od == 1) {
        while (top[x] != 1) {
            ans += query1(1, 1, n, l[top[x]], l[x]);//查询未安装数量
            modify(1, 1, n, l[top[x]], l[x], -1);//将所有都安装
            x = fa[top[x]];
        }
        ans += query1(1, 1, n, l[top[x]], l[x]);
        modify(1, 1, n, l[top[x]], l[x], -1);
    }
    else {
        ans += query2(1, 1, n, l[x], r[x]);
        modify(1, 1, n, l[x], r[x], 1);//将所有都卸载
    }
    return ans;
}
int main() {
    n = read();
    for (int i = 2; i <= n; i++) {
        int a; cin >> a;
        mp[a + 1].push_back(i);
        mp[i].push_back(a + 1);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    m = read();
    for (int i = 1; i <= m; i++) {
        string s; int od;
        cin >> s >> od; od++;
        if (s == "install") {
            //如果是安装的话，只用统计该点开始到根的未安装软件多少即可
            cout << query(od, 1) << endl;
        }
        else {
            //如果是要卸载的话，统计子树中已安装的软件，并且将dfs序区间全部清0即可
            cout << query(od, -1) << endl;
        }
    }
    return 0;
}