BZOJ 4196: [Noi2015]軟體包管理器

題目連結：​​傳送門​​​

Description

Linux使用者和OSX使用者一定對軟體包管理器不會陌生。通過軟體包管理器，你可以通過一行指令安裝某一個軟體包，然後軟體包管理器會幫助你從軟體源下載下傳軟體包，同時自動解決所有的依賴（即下載下傳安裝這個軟體包的安裝所依賴的其它軟體包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的homebrew都是優秀的軟體包管理器。

.

你決定設計你自己的軟體包管理器。不可避免地，你要解決軟體包之間的依賴問題。如果軟體包A依賴軟體包B，那麼安裝軟體包A以前，必須先安裝軟體包B。同時，如果想要解除安裝軟體包B，則必須解除安裝軟體包A。現在你已經獲得了所有的軟體包之間的依賴關系。而且，由于你之前的工作，除0号軟體包以外，在你的管理器當中的軟體包都會依賴一個且僅一個軟體包，而0号軟體包不依賴任何一個軟體包。依賴關系不存在環（若有m(m≥2)個軟體包A1,A2,A3,…,Am，其中A1依賴A2，A2依賴A3，A3依賴A4，……，Am−1依賴Am，而Am依賴A1，則稱這m個軟體包的依賴關系構成環），當然也不會有一個軟體包依賴自己。

現在你要為你的軟體包管理器寫一個依賴解決程式。根據回報，使用者希望在安裝和解除安裝某個軟體包時，快速地知道這個操作實際上會改變多少個軟體包的安裝狀态（即安裝操作會安裝多少個未安裝的軟體包，或解除安裝操作會解除安裝多少個已安裝的軟體包），你的任務就是實作這個部分。注意，安裝一個已安裝的軟體包，或解除安裝一個未安裝的軟體包，都不會改變任何軟體包的安裝狀态，即在此情況下，改變安裝狀态的軟體包數為0。

Input

輸入檔案的第1行包含1個正整數n，表示軟體包的總數。軟體包從0開始編号。

随後一行包含n−1個整數，相鄰整數之間用單個空格隔開，分别表示1,2,3,…,n−2,n−1号軟體包依賴的軟體包的編号。

接下來一行包含1個正整數q，表示詢問的總數。

之後q行，每行1個詢問。詢問分為兩種：

installx：表示安裝軟體包x

uninstallx：表示解除安裝軟體包x

你需要維護每個軟體包的安裝狀态，一開始所有的軟體包都處于未安裝狀态。對于每個操作，你需要輸出這步操作會改變多少個軟體包的安裝狀态，随後應用這個操作（即改變你維護的安裝狀态）。

Output

輸出檔案包括q行。

輸出檔案的第i行輸出1個整數，為第i步操作中改變安裝狀态的軟體包數。

Sample Input

7

0 0 0 1 1 5

5

install 5

install 6

uninstall 1

install 4

uninstall 0

Sample Output

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define
 
using namespace std;
typedef long long ll;
struct node {
    int next, to;
}edge[A];
int head[A], num_edge;
void add_edge(int from, int to) {
    edge[++num_edge].next = head[from];
    edge[num_edge].to = to;
    head[from] = num_edge;
}
int dfn[A], top[A], fa[A], dep[A], siz[A], son[A], pre[A];
int n, q, cnt, w, x, a, b, c;
namespace SegmentTree {
    struct Treenode {
        int l, r, w, f;
    }tree[A];
    void update(int k) {
        tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w;
    }
    void down(int k) {
        tree[k << 1].f = tree[k].f;
        tree[k << 1 | 1].f = tree[k].f;
        tree[k << 1].w = (tree[k << 1].r - tree[k << 1].l + 1) * tree[k].f;
        tree[k << 1 | 1].w = (tree[k << 1 | 1].r - tree[k << 1 | 1].l + 1) * tree[k].f;
        tree[k].f = -1;
    }
    void build(int k ,int l, int r) {
        tree[k].l = l;
        tree[k].r = r;
        if (l == r) {
            tree[k].w = 0;
            tree[k].f = -1;
            return;
        }
        int m = (l + r) >> 1;
        build(k << 1, l, m);
        build(k << 1 | 1, m + 1, r);
        update(k);
    }
    void set01(int k) {
        if (tree[k].l >= a and tree[k].r <= b) {
            tree[k].w = (tree[k].r - tree[k].l + 1) * c;
            tree[k].f = c;
            return;
        }
        if (tree[k].f != -1) down(k);
        int m = (tree[k].l + tree[k].r) >> 1;
        if (a <= m) set01(k << 1);
        if (b > m) set01(k << 1 | 1);
        update(k);
    }
}
void prepare(int fr) {
    siz[fr] = 1;
    for (int i = head[fr]; i; i = edge[i].next) {
        int ca = edge[i].to;
        if (ca == fa[fr]) continue;
        fa[ca] = fr;
        dep[ca] = dep[fr] + 1;
        prepare(ca);
        siz[fr] += siz[ca];
        if (siz[ca] > siz[son[fr]]) son[fr] = ca;
    }
}
void dfs(int fr, int tp) {
    dfn[fr] = ++cnt, pre[cnt] = fr, top[fr] = tp;
    if (!son[fr]) return;
    dfs(son[fr], tp);
    for (int i = head[fr]; i; i = edge[i].next) {
        int ca = edge[i].to;
        if (ca == fa[fr] or ca == son[fr]) continue;
        dfs(ca, ca);
    }
}
void change(int x, int y, bool val) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        a = dfn[top[x]], b = dfn[x], c = val;
        SegmentTree::set01(1);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    a = dfn[x], b = dfn[y], c = val;
    SegmentTree::set01(1);
}
 
int main(int argc, char const *argv[]) {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &w);
        w++;
        add_edge(i, w);
        add_edge(w, i);
    }
    dep[1] = 1;
    prepare(1);
    dfs(1, 1);
    SegmentTree::build(1, 1, n);
    scanf("%d", &q);
    while (q--) {
        char opt[10];
        scanf("%s%d", opt, &x);
        x++;
        int f1 = SegmentTree::tree[1].w;
        if (opt[0] == 'i') {
            change(1, x, 1);
            printf("%d\n", abs(f1 - SegmentTree::tree[1].w));
        }
        if (opt[0] == 'u') {
            a = dfn[x], b = dfn[x] + siz[x] - 1, c = 0;
            SegmentTree::set01(1);
            printf("%d\n", abs(f1 - SegmentTree::tree[1].w));
        }
    }
}