记录编号	308965	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	11.242 s
提交时间	2016-09-18 20:16:50	内存使用	8.37 MiB

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <list>
#include <vector>
#include <queue>
#include <string.h>
#include <string>
#include <cctype>
using namespace std;
int fast_read()
{
    int r;
    char c;
    bool sig = false;
    while(c = getchar())    
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')
            sig = true;
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    if(sig)return -r;
    return r;
}
#define MAXN 100002
struct edge
{
    int from, to;
    inline void read()
    {
        from = fast_read();
        to = fast_read();
    }
};
vector<int> G[MAXN];
edge edges[MAXN];
int top[MAXN], parent[MAXN], son[MAXN], size[MAXN], deep[MAXN];
int has[MAXN], uhas[MAXN];
int last[MAXN];
int hasid = 0;
void dfs1(int u, int f, int d)
{
    deep[u] = d;
    parent[u] = f;
    size[u] = 1;
    //son[u] = -1;     //注意0是有意义的
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != f)
        {
            dfs1(to, u, d+1);
            size[u] += size[to];
            if(son[u] == -1)
                son[u] = to;
            else if(size[to] > size[son[u]])
                son[u] = to;
        }
    }
}
void dfs2(int u, int tp)
{
    top[u] = tp;
    has[u] = ++hasid;
    //uhas[has[u]] = u;
    if(son[u] != -1)
        dfs2(son[u], tp);
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != son[u] && to != parent[u])
            dfs2(to, to);
    }
    last[u] = hasid;
}
   
struct node
{
    int l, r;
    int ls, rs; 
    int cnt;
    int lazy;
    void setv()
    {
        cnt = lazy*(r-l+1);
    }
}ns[MAXN<<1];
int root = 1;
int _last = root;  //撞了...
void pushup(int c)
{
    if(!c)return;
    node &d = ns[c];
    d.cnt = ns[d.ls].cnt + ns[d.rs].cnt;
}
int build(int l, int r)
{
    if(l > r)return 0;
    int cur = _last++;
    node &d = ns[cur];
    d.l = l;
    d.r = r;
    d.lazy = -1;
    d.cnt = 0;
    if(l == r)
        d.cnt = 0;
    else
    {
        int m = (l+r)>>1;
        if(l <= m)
        {
            d.ls = build(l, m);
            d.rs = build(m+1, r);
        }
    }
    //pushup(cur);
    return cur;
}
void pushdown(int c)
{
    node &d = ns[c];
    if(d.lazy != -1)
    {
        ns[d.ls].lazy = ns[d.rs].lazy = d.lazy;
        ns[d.ls].setv();
        ns[d.rs].setv();
        d.lazy = -1;
    }
}
void setval(int c, int l, int r, int v)
{
    if(!c)return;
    node &d = ns[c];
    if(l == d.l && r == d.r)
    {
        d.lazy = v;
        d.setv();
    }else
    {
        pushdown(c);
        if(l >= ns[d.rs].l)
            setval(d.rs, l, r, v);
        else if(r <= ns[d.ls].r)
            setval(d.ls, l, r, v);
        else
        {
            setval(d.ls, l, ns[d.ls].r, v);
            setval(d.rs, ns[d.rs].l, r, v);
        }
        pushup(c);
    }
}
int query(int c, int l, int r)
{
    if(!c)return 0;
    node &d = ns[c];
    if(l == d.l && r == d.r)
    {
        return d.cnt;
    }else
    {
        pushdown(c);
        if(l >= ns[d.rs].l)
            return query(d.rs, l, r);
        else if(r <= ns[d.ls].r)
            return query(d.ls, l, r);
        else
            return query(d.ls, l, ns[d.ls].r) + query(d.rs, ns[d.rs].l, r); 
    }
}
void clear(int n)
{
    while(n--)getchar();
}
int install(int x)
{
    int ans = 0;
    while(x != -1)
    {
        int t = top[x];
        int l = has[t];
        int r = has[x];
        ans += r-l+1-query(1, l, r);
        setval(1, l, r, 1);
        x = parent[t];
    }
    return ans;
}
int uninstall(int x)
{
    int r = query(1, has[x], last[x]);
    setval(1, has[x], last[x], 0);
    return r;
}
int main()
{
    freopen("manager.in", "r", stdin);
    freopen("manager.out", "w", stdout);
    int n;    
    n = fast_read();
    for(int i = 1; i < n; i++)
    {
        int x = fast_read();
        edge &e = edges[i];
        e.from = i;
        e.to = x;
        G[e.from].push_back(e.to);
        G[e.to].push_back(e.from);
    }
    memset(son, 0xff, sizeof(son));
    dfs1(0, -1, 1);
    dfs2(0, 0);
    build(1, hasid);
    int q = fast_read();
    while(q--)
    {
        char c;
        int arg;
        while(c = getchar())
            if(c == 'i' || c == 'u')break;
        switch(c)
        {
            case 'i':
                clear(6);
                arg = fast_read();
                printf("%d\n", install(arg));
            break;
            case 'u':
                clear(8);
                arg = fast_read();
                printf("%d\n", uninstall(arg));
            break;
        }
    }
    return 0;
}

/*
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 1

3
1
3
2
3
*/