软件包管理器问题

解题思路

本题定义了一个依赖关系，如果 $A$ 依赖 $B$，则安装 $A$ 之前需要先安装 $B$，卸载 $B$ 之前需要先卸载 $A$。然后会给我们若干个依赖关系。

如果我们将 $A$ 依赖 $B$ 看作一条从 $B$ 连向 $A$ 的有向边，即 $B$ 是 $A$ 的父节点，这样所有的依赖关系就会构成一张图，由于每个节点有且仅有一个依赖的软件，所以整个图其实是一棵树的结构，又因为 $0$ 号点没有需要依赖的软件，相当于没有父节点，所以 $0$ 号点就是整棵树的父节点。这里为方便我们将节点编号改成从 $1$ 开始，此时 $1$ 号点就是根节点。

此时如果我们想要安装一个软件 $u$，那么我们就需要将 $u$ 到 $1$ 号点路径上的所有软件都安装好，才能安装 $u$。反之，如果我们想要卸载一个软件 $u$，那么我们就需要将以 $u$ 为根节点的整棵子树全部卸载掉，才能卸载 $u$。而每个节点的状态显然只有两种，已安装和未安装，记作 $1$ 和 $0$。

那么我们要想安装一个节点 $u$，就是将 $1$ 到 $u$ 的路径上的所有点的状态变成 $1$。要想卸载一个节点 $u$，就是将以 $u$ 为根节点的子树中所有点的状态变成 $0$。

显然本题的两个操作就是修改树上某一条路径和修改树上某一棵子树，而两个树上操作我们都能用树链剖分的思想转化为区间操作来实现。

然后本题在每次操作之前，还需要输出一下当前操作会更改多少个节点的状态，对于安装操作，就是将是 $0$ 的状态变成了 $1$，对于写在操作，就是将是 $1$ 的状态变成了 $0$，因此我们可以用一个信息记录一下每个区间的权值和，假设操作前区间中的权值和为 $a$，操作后区间中的权值和为 $b$，对于安装操作，显然满足 $a \leq b$，此时改变状态的节点数就是 $b - a$。对于卸载操作，显然满足 $a \geq b$，此时改变状态的节点数就是 $a - b$。因此我们分别在操作前和操作后求一些权值和，就能知道改变状态的节点数。

以上操作都可以通过树链剖分转化成若干个区间的操作，而要实现的区间操作就是将某个区间中的数都变成一个数。另外还有一个查询整个区间的权值和的操作，这两个操作我们都可以用线段树来实现，实际上查询操作直接查询根节点的信息即可，因此其实只需要实现一个区间修改操作。对于区间修改操作我们需要维护一个懒标记 $flag$，为 $-1$ 表示当前区间不需要修稿，为 $1$ 表示当前区间每个数变成 $1$，为 $0$ 表示当前区间每个数变成 $0$。这里规定当前区间的懒标记表示需要对子节点进行的操作。还需要记录一个 $sum$ 表示权值和。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

struct Node
{
    int l, r;
    //权值和、子节点中每个数是否需要修改，-1 不修改，0 修改为 0，1 修改为 1（懒标记）
    int sum, flag;
}tr[N * 4]; //线段树

int n, m;
int h[N], e[N], ne[N], idx; //邻接表
//id[i] 表示节点 i 的 dfs 序的编号
//cnt[i] 表示以节点 i 为根节点的子树中的节点个数
//top[i] 表示节点 i 所在的重链的顶点
//fa[i] 表示节点 i 的父节点
//son[i] 表示节点 i 的重儿子
//timstamp 表示 dfs 序的时间戳
int id[N];
int d[N], cnt[N], timestamp;
int top[N], fa[N], son[N];

void add(int a, int b) //添加边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

//预处理每个节点的深度、重儿子、所在子树中节点个数等信息
void dfs1(int u, int depth)
{
    d[u] = depth, cnt[u] = 1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs1(j, depth + 1);
        cnt[u] += cnt[j];
        if(cnt[son[u]] < cnt[j]) son[u] = j;
    }
}

//找出所有重链，并预处理每个节点的编号、所在重链的顶点等信息
void dfs2(int u, int t)
{
    id[u] = ++timestamp, top[u] = t;
    if(!son[u]) return;
    dfs2(son[u], t);
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == son[u]) continue;
        dfs2(j, j);
    }
}

void pushup(int u) //用子节点的信息得到当前节点的信息
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) //将当前节点的懒标记下传给子节点
{
    Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if(root.flag != -1)
    {
        left.sum = root.flag * (left.r - left.l + 1), left.flag = root.flag;
        right.sum = root.flag * (right.r - right.l + 1), right.flag = root.flag;
        root.flag = -1;
    }
}

void build(int u, int l, int r) //初始化邻接表
{
    tr[u] = {l, r, 0, -1};
    if(l == r) return;

    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int k) //区间修改
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].flag = k; 
        tr[u].sum = k * (tr[u].r - tr[u].l + 1);
        return;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify(u << 1, l, r, k);
    if(r > mid) modify(u << 1 | 1, l, r, k);
    pushup(u);
}

void modify_path(int u, int v, int k) //将 u 到 v 的路径上所有点的权值变成 k
{
    while(top[u] != top[v])
    {
        if(d[top[u]] < d[top[v]]) swap(u, v);
        modify(1, id[top[u]], id[u], k);
        u = fa[top[u]];
    }
    if(d[u] < d[v]) swap(u, v);
    modify(1, id[v], id[u], k);
}

void modify_tree(int u, int k) //将以 u 为根节点的子树中所有点的权值变成 k
{
    modify(1, id[u], id[u] + cnt[u] - 1, k);
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    //建树
    for(int i = 2; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        x++; //下标从 1 开始，每个节点的编号 + 1
        add(x, i); //i 依赖 x，从 x 向 i 连一条有向边
        fa[i] = x; //记录每个节点的父节点
    }

    dfs1(1, 1); //预处理每个节点的深度、重儿子、所在子树中节点个数等信息
    dfs2(1, 1);
    build(1, 1, n);

    scanf("%d", &m);
    char op[20];
    int u;
    while(m--)
    {
        scanf("%s%d", op, &u);
        u++; //下标从 1 开始，节点编号 + 1
        if(!strcmp(op, "install")) //安装 u
        {
            int a = tr[1].sum; //记录操作前的权值和
            modify_path(1, u, 1); //将根节点到 u 的路径上所有点的权值变成 1
            int b = tr[1].sum; //记录操作后的权值和
            printf("%d\n", b - a); //此时改变状态的节点个数为 b - a
        }
        else //卸载 u
        {
            int a = tr[1].sum; //记录操作前的权值和
            modify_tree(u, 0); //将以 u 为根节点的子树中所有点的权值变成 0
            int b = tr[1].sum; //记录操作后的权值和
            printf("%d\n", a - b); //此时改变状态的节点个数为 a - b
        }
    }
    return 0;
}