Steven_Meng's Blog

传送门

安装操作其实就是把这个节点及其祖先节点变成$1$，卸载操作其实就是把这个节点及其子树之内的所有节点变成$0$

树链剖分实现即可。

#include <cstdio>
#include <iostream>
#include <vector>
#define MAXN 100005
using namespace std;
vector<int> G[MAXN];
char cmd[10];
int fa[MAXN], size[MAXN], Bigson[MAXN], top[MAXN], id[MAXN], dep[MAXN];
int cnt;
int fro[MAXN], bac[MAXN];
void dfs(int u, int father)
{
    size[u] = 1;
    Bigson[u] = 0;
    dep[u] = dep[father] + 1;
    for (int i = 0; i < G[u].size(); i++)
    {
        if (G[u][i] != father)
        {
            fa[G[u][i]] = u;
            dfs(G[u][i], u);
            size[u] += size[G[u][i]];
            if (size[G[u][i]] > size[Bigson[u]])
            {
                Bigson[u] = G[u][i];
            }
        }
    }
}
void dfs2(int u, int Top)
{
    top[u] = Top;
    id[u] = ++cnt;
    fro[cnt] = u;
    if (Bigson[u])
    {
        dfs2(Bigson[u], Top);
    }
    for (int i = 0; i < G[u].size(); i++)
    {
        if (G[u][i] != fa[u] && G[u][i] != Bigson[u])
        {
            dfs2(G[u][i], G[u][i]);
        }
    }
}
struct SegmentTree
{
    struct node
    {
        int l, r;
        int val, tag;
    } tree[MAXN << 2];
    void pushup(int i)
    {
        tree[i].val = tree[i << 1].val + tree[i << 1 | 1].val;
    }
    void pushdown(int i)
    {
        if (tree[i].tag != -1)
        {
            tree[i << 1].tag = tree[i << 1 | 1].tag = tree[i].tag;
            tree[i << 1].val = tree[i].tag * (tree[i << 1].r - tree[i << 1].l + 1);
            tree[i << 1 | 1].val = tree[i].tag * (tree[i << 1 | 1].r - tree[i << 1 | 1].l + 1);
            tree[i].tag = -1;
        }
    }
    void build(int l, int r, int i)
    {
        tree[i].l = l;
        tree[i].r = r;
        tree[i].val = 0;
        tree[i].tag = -1;
        if (l == r)
        {
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, i << 1);
        build(mid + 1, r, i << 1 | 1);
    }
    void update(int L, int R, int i, int v)
    {
        int l = tree[i].l, r = tree[i].r;
        if (L <= l && r <= R)
        {
            tree[i].val = v * (r - l + 1);
            tree[i].tag = v;
            return;
        }
        pushdown(i);
        int mid = (l + r) >> 1;
        if (L <= mid)
        {
            update(L, R, i << 1, v);
        }
        if (mid < R)
        {
            update(L, R, i << 1 | 1, v);
        }
        pushup(i);
    }
} Seg;
void update_tree(int u, int v)
{
    int topu = top[u];
    int topv = top[v];
    while (topu != topv)
    {
        if (dep[topu] < dep[topv])
        {
            swap(u, v);
            swap(topu, topv);
        }
        Seg.update(id[topu], id[u], 1, 1);
        u = fa[topu];
        topu = top[u];
    }
    if (dep[u] > dep[v])
    {
        swap(u, v);
    }
    Seg.update(id[u], id[v], 1, 1);
}
int Myabs(int a, int b)
{
    return (a - b > 0) ? a - b : b - a;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 2; i <= n; i++)
    {
        int k;
        scanf("%d", &k);
        G[++k].push_back(i);
        G[i].push_back(k);
    }
    dfs(1, 1);
    dfs2(1, 1);
    Seg.build(1, n, 1);
    int q;
    scanf("%d", &q);
    while (q--)
    {
        scanf("%s", cmd);
        int Sum = Seg.tree[1].val; //初始值
        if (cmd[0] == 'i')
        {
            int x;
            scanf("%d", &x);
            ++x;
            update_tree(1, x);
        }
        else if (cmd[0] == 'u')
        {
            int x;
            scanf("%d", &x);
            ++x;
            Seg.update(id[x], id[x] + size[x] - 1, 1, 0);
        }
        printf("%d\n", Myabs(Sum, Seg.tree[1].val));
    }
}