Description

Linux 用户和 OSX 用户一定对软件包管理器不会陌生. 通过软件包管理器, 你可以通过一行命令安装某一个软件包, 然后软件包管理器会帮助你从软件源下载软件包, 同时自动解决 所有的依赖 (即下载安装这个软件包的安装所依赖的其它软件包), 完成所有的配置. Debian/Ubuntu 使用的 apt-get, Fedora/CentOS 使用的 yum, 以及 OSX 下可用的 homebrew 都是优秀的软件包管理器.

你决定设计你自己的软件包管理器. 不可避免地, 你要解决软件包之间的依赖问题. 如果 软件包 A 依赖软件包 B, 那么安装软件包 A 以前, 必须先安装软件包 B. 同时, 如果想要卸载 软件包 B, 则必须卸载软件包 A. 现在你已经获得了所有的软件包之间的依赖关系. 而且, 由于你之前的工作, 除 \(0\) 号软件包以外, 在你的管理器当中的软件包都会依赖一个且仅 一个软件包, 而 \(0\) 号软件包不依赖任何一个软件包. 依赖关系不存在环 (若有 \(m (m \gt 2)\) 个软件包 \(A_1, A_2, A_3, \ldots, A_m\), 其中 \(A_1\) 依赖 \(A_2\),\(A_2\) 依赖 \(A_3\),\(A_3\) 依赖 \(A_4\), ...... ,\(A_{m-1}\) 依赖 \(A_m\), 而 \(A_m\) 依赖 \(A_1\), 则称这 \(m\) 个软件包的依赖关系构成环), 当然也不会有一个软件包依赖自己.

现在你要为你的软件包管理器写一个依赖解决程序. 根据反馈, 用户希望在安装和卸载某个 软件包时, 快速地知道这个操作实际上会改变多少个软件包的安装状态 (即安装操作会安装 多少个未安装的软件包, 或卸载操作会卸载多少个已安装的软件包), 你的任务就是实现 这个部分. 注意, 安装一个已安装的软件包, 或卸载一个未安装的软件包, 都不会改变任何软件包的安装状态, 即在此情况下, 改变安装状态的软件包数为 \(0\).

Input

输入文件的第 \(1\) 行包含 \(1\) 个正整数 \(n\), 表示软件包的总数. 软件包从 \(0\) 开始编号.

随后一行包含 \(n - 1\) 个整数, 相邻整数之间用单个空格隔开, 分别表示 \(1, 2, 3, \ldots, n-2, n-1\) 号软件包依赖的软件包的编号.

接下来一行包含 \(1\) 个正整数 \(q\), 表示询问的总数.

之后 \(q\) 行, 每行 \(1\) 个询问. 询问分为两种:

  • install x: 表示安装软件包 \(x\);
  • uninstall x: 表示卸载软件包 \(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

3
1
3
2
3

Data Range

对于所有数据, 满足:\(n \leq 10^5, q \leq 10^5\)

Explanation

典型树链剖分 (轻重链剖分) 模板题.

由于树链剖分是一个根据 DFS 序标号的结构, 所以一棵子树的节点编号 (新编的号) 一定是连续的, 为其根节点编号到子树中最大的编号. 这样一来, 在线段树上就可以对整棵子树进行批量操作, 时间复杂度为 \(O(\log n)\).

进一步地, 线段树应该为 “设置值” 操作而不是 “修改值” 操作, 这一点需要注意一下.

(把右子写成了左子是什么情况啊...... )

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 200010, maxt = maxn << 2;

class SegmentTree { public:
    struct node { node *lc, *rc;
        int sum, lazy, lb, mb, rb; } *root, npool[maxt];
    int n, ncnt;
    node* make_node(void) { node *p = &npool[++ncnt];
        p->lc = p->rc = NULL; p->sum = 0; p->lazy = -1;
        p->lb = p->mb = p->rb = 0; return p; }
    void dispatch_lazy(node *p) { if (p->lazy == -1) return ;
        if (p->lc) p->lc->sum = (p->lc->rb - p->lc->lb + 1) * p->lazy, p->lc->lazy = p->lazy;
        if (p->rc) p->rc->sum = (p->rc->rb - p->rc->lb + 1) * p->lazy, p->rc->lazy = p->lazy;
        p->lazy = -1; return ; }
    void change(node *p, int l, int r, int v) {
        if (p->lb == l && p->rb == r) { p->lazy = v;
            p->sum = (p->rb - p->lb + 1) * v; return ; }
        dispatch_lazy(p);
        if (r <= p->mb) change(p->lc, l, r, v);
        else if (l > p->mb) change(p->rc, l, r, v);
        else change(p->lc, l, p->mb, v), change(p->rc, p->mb+1, r, v);
        p->sum = p->lc->sum + p->rc->sum;
        return ; }
    void change(int l, int r, int v) {
        return this->change(root, l, r, v); }
    int query(node *p, int l, int r) {
        if (p->lb == l && p->rb == r) { return p->sum; }
        dispatch_lazy(p);
        if (r <= p->mb) return query(p->lc, l, r);
        else if (l > p->mb) return query(p->rc, l, r);
        return query(p->lc, l, p->mb) + query(p->rc, p->mb+1, r); }
    int query(int l, int r) {
        return this->query(root, l, r); }
    node* build_tree(int l, int r) {
        if (l == r) { node *p = make_node();
            p->lb = p->mb = p->rb = l; return p; }
        int mid = (l + r) >> 1; node *p = make_node();
        p->lb = l; p->mb = mid; p->rb = r;
        p->lc = build_tree(l, mid); p->rc = build_tree(mid + 1, r);
        return p; }
    void build_tree(int n) { this->n = n;
        this->root = this->build_tree(1, n);
        return ; }
} st;

class HeavyLightDecomposition { public:
    struct edge { int u, v; edge *next;
        } *edges[maxn], epool[maxn];
    int n, root, ecnt, dcnt, size[maxn], par[maxn], depth[maxn],
        maxch[maxn], ctop[maxn], last[maxn], edgenum[maxn];
    void add_edge(int u, int v) { edge *p = &epool[++ecnt];
        p->u = u; p->v = v; p->next = edges[u];
        edges[u] = p; return ; }
    void dfs1(int p) { size[p] = 1;
        for (edge *ep = edges[p]; ep; ep = ep->next) if (ep->v != par[p]) {
            par[ep->v] = p; depth[ep->v] = depth[p] + 1;
            dfs1(ep->v); size[p] += size[ep->v];
            if (size[ep->v] > size[maxch[p]]) maxch[p] = ep->v;
        } return ; }
    void dfs2(int p, int chaintop) {
        edgenum[p] = ++dcnt; ctop[p] = chaintop;
        if (maxch[p]) dfs2(maxch[p], chaintop);
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (ep->v != par[p] && ep->v != maxch[p])
                dfs2(ep->v, ep->v);
        last[p] = dcnt; return ; }
    void perform_init(int n) { this->n = n;
        root = 1; dfs1(root); dfs2(root, root);
        st.build_tree(n); return ; }
    int perform_install(int x) {
        int a = root, b = x, f1 = ctop[a], f2 = ctop[b],
            res = depth[b] - depth[a] + 1;
        while (f1 != f2) {
            if (depth[f1] < depth[f2])
                swap(f1, f2), swap(a, b);
            res -= st.query(edgenum[f1], edgenum[a]);
            st.change(edgenum[f1], edgenum[a], 1);
            a = par[f1], f1 = ctop[a]; }
        if (depth[a] > depth[b]) swap(a, b);
        res -= st.query(edgenum[a], edgenum[b]);
        st.change(edgenum[a], edgenum[b], 1);
        return res; }
    int perform_uninstall(int x) {
        int res = st.query(edgenum[x], last[x]);
        st.change(edgenum[x], last[x], 0);
                return res; }
} hld;

int n, Q;
char str[32];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 2, x; i <= n; i++) scanf("%d", &x),
        hld.add_edge(x + 1, i);
    hld.perform_init(n);
    scanf("%d", &Q);
    for (int i = 1, x; i <= Q; i++) {
        scanf("%s%d", str, &x); x += 1;
        if (str[0] == 'i')
            printf("%d\n", hld.perform_install(x));
        else
            printf("%d\n", hld.perform_uninstall(x));
    }
    return 0;
}