0.题目描述

题面:[NOI2015] 软件包管理器

这道题是关于linux的软件依赖关系。

依赖关系成一颗以 0 号软件为根的树。求安装或删除一个软件需要更改的软件包数

1.做题经历

这个题我一上来半个小时左右就想到了解法，但是到今天才实现，因为他实在是太恶心，代码量太大，没办法。做题的过程中重写了两次代码，第二次疯狂调试，最后才调对。提前提醒大家不要放弃

2.解析

2.1 思路

之前也提到了这道题可以抽象成一颗以 0 为根的树进行思考：

• 安装一个软件 a ，需要安装从 a 到 0 路径上所有的软件

• 卸载一个软件 b，需要卸载以 b 为根的子树中的所有软件

由此可知这道题和树上的区间修改查询有关，可以用树链剖分来做。

2.2 实现

下文中的数组的声明和函数原型为：

int dep[N], cnt[N]; // 深度 子树节点个数
int id[N] // 树上的每个点映射到线段树上的位置

void modify(int u, int l, int r, int k); // 线段树区间修改
void modify(int x, int y, int k); // 树剖区间修改
void query(int u, int l, int r); // 线段树区间查询
void query(int x, int y); // 树剖区间查询

一个软件只有两个状态：已安装，未安装。为了方便统计，计已安装为 1, 未安装为 0 由此可知：

• 安装一个软件 a，需要安装的软件数量为 dep[a] - query(0, a)，执行的操作是 modify(0,a,1)

• 卸载一个软件 b，需要卸载的软件数量为 query(1, id[b], id[b] + cnt[b] - 1) ，执行的操作是 modify(1, id[b].id[b]+cnt[b]-1,0)

实现的思路也很简单，难的是这道题有很多的坑，一不小心就进去了 awa

2.3 坑

1. 从 0 编号改成从 1 编号

   问题：如果从 0 编号链式前向星和线段树都会出一些诡异的问题，莫名其妙得搜索直接挂了，线段树都是 0 (可能是我太弱了)

   解决：把读入的每个点的编号都加 1

2. 线段树直接赋值

   问题：难以计算每个点需要加多少，因为有的点不用加，有的点用加 (软件已经装了不用再装一次)

   解决：安装时直接把区间赋值成区间长度，卸载时直接将区间改成 0

到这里问题就已经解决了，思路简单也好理解，就是写代码很艰难，最后贴上我的代码，实在写不出来了或者找不出错的可以参考一下，里面也有一些调试的思路。

Ac Code

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100010;

struct SegmentTree{
    int l, r;
    int val, lazy;
    // 这颗树中 lazy 的有效值只能是 0 或 1, 把 lazy 的初值赋成 -1 以防更新错误(下放懒标记时, 全成 0 了)
    SegmentTree() {lazy = -1;}
}tr[N * 4];

int nxt[N], ver[N], head[N];
int tot;

int fa[N], dep[N], son[N], cnt[N];
int id[N], rnk[N], top[N];
int times;

void add(int x, int y ) {
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}

void dfs(int x) {
    cnt[x] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
        int &y = ver[i];
        if (y == fa[x]) continue;
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs(y);
        cnt[x] += cnt[y];
        if (cnt[son[x]] < cnt[y]) son[x] = y;
    }
}

void dfs(int x, int tp) {
    top[x] = tp;
    id[x] = ++times;
    rnk[times] = x;
    if (!son[x]) return;
    dfs(son[x], tp);
    for (int i = head[x]; i; i = nxt[i]) {
        int &y = ver[i];
        if (y == fa[x] || y == son[x]) continue;
        dfs(y, y);
    }
}

void push_up(int u) {
    tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}

void push_down(int u) { // 要装这个区间内的都得装, 同样, 要卸都得卸
    if (tr[u].lazy == -1) return; // 没有懒标记的不算
    tr[u << 1].lazy = tr[u].lazy;
    tr[u << 1 | 1].lazy = tr[u].lazy;
    tr[u << 1].val = tr[u].lazy * (tr[u << 1].r - tr[u << 1].l + 1);
    tr[u << 1 | 1].val = tr[u].lazy * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
    tr[u].lazy = -1; // 清空后变成 -1, 不要改成 0, 0也是有效数字, 否则下放懒标记后都成 0 了
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) return; // 直接就是 0, 默认都没装
    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 (l <= tr[u].l && tr[u].r <= r) {
        // 注意，直接赋值，否则还得多写一个 query 增大常数时间复杂度还容易错
        tr[u].lazy = k;
        tr[u].val = k * (tr[u].r - tr[u].l + 1);
    }
    else {
        push_down(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);
        push_up(u);
    }
}

void modify(int x, int y, int k) {
    while (top[x] != top[y]) {
        if (dep[top[x]] > dep[top[y]]) swap(x, y);
        modify(1, id[top[y]], id[y], k);
        y = fa[top[y]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    modify(1, id[x], id[y], k);
}

int query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
    else {
        push_down(u);
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if (l <= mid) res += query(u << 1, l, r);
        if (r > mid) res += query(u << 1 | 1, l, r);
        return res;
    }
}

int query(int x, int y) {
    int res = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] > dep[top[y]]) swap(x, y);
        res += query(1, id[top[y]], id[y]);
        y = fa[top[y]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    res += query(1, id[x], id[y]);
    return res;
}

void print(int u) { // 检查线段树用的，输出每个点的值
    if (tr[u].l == tr[u].r) {
        printf("%d ", tr[u].val);
    }
    else {
        push_down(u); // 记得下放懒标记
        print(u << 1), print(u << 1 | 1);
    }
}

int main() {
    int n, m;
    scanf("%d", &n);
    for (int i = 2; i <= n; ++i) { // 一定要这么写, 后果不堪设想
        int t;
        scanf("%d", &t);
        add(t + 1, i);
    }
    dep[1] = 1;
    dfs(1);
    dfs(1, 1);
    build(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        string s;
        int t;
        cin >> s, scanf("%d", &t);
        ++t; // 一定要这么写, 后果不堪设想
        if (s == "install") {
            printf("%d\n", dep[t] - query(1, t));
            modify(1, t, 1);
        }
        else {
            printf("%d\n", query(1, id[t], id[t] + cnt[t] - 1));
            modify(1, id[t], id[t] + cnt[t] - 1, 0);
        }
    }
    return 0;
}