0.题目描述#

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

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

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

1.做题经历#

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

2.解析#

2.1 思路#

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

安装一个软件 a ，需要安装从 a 到 0 路径上所有的软件
卸载一个软件 b，需要卸载以 b 为根的子树中的所有软件

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

2.2 实现#

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

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

4
void modify(int u, int l, int r, int k); // 线段树区间修改
5
void modify(int x, int y, int k); // 树剖区间修改
6
void query(int u, int l, int r); // 线段树区间查询
7
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 坑#

从 0 编号改成从 1 编号

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

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

线段树直接赋值

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

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

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

Ac Code#

1
#include <cstdio>
2
#include <iostream>
3

4
using namespace std;
5

6
const int N = 100010;
7

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

15
int nxt[N], ver[N], head[N];
16
int tot;
17

18
int fa[N], dep[N], son[N], cnt[N];
19
int id[N], rnk[N], top[N];
20
int times;
21

22
void add(int x, int y ) {
23
    ver[++tot] = y;
24
    nxt[tot] = head[x];
25
    head[x] = tot;
26
}
27

28
void dfs(int x) {
29
    cnt[x] = 1;
30
    for (int i = head[x]; i; i = nxt[i]) {
31
        int &y = ver[i];
32
        if (y == fa[x]) continue;
33
        fa[y] = x;
34
        dep[y] = dep[x] + 1;
35
        dfs(y);
36
        cnt[x] += cnt[y];
37
        if (cnt[son[x]] < cnt[y]) son[x] = y;
38
    }
39
}
40

41
void dfs(int x, int tp) {
42
    top[x] = tp;
43
    id[x] = ++times;
44
    rnk[times] = x;
45
    if (!son[x]) return;
46
    dfs(son[x], tp);
47
    for (int i = head[x]; i; i = nxt[i]) {
48
        int &y = ver[i];
49
        if (y == fa[x] || y == son[x]) continue;
50
        dfs(y, y);
51
    }
52
}
53

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

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

67
void build(int u, int l, int r) {
68
    tr[u].l = l, tr[u].r = r;
69
    if (l == r) return; // 直接就是 0, 默认都没装
70
    int mid = l + r >> 1;
71
    build (u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
72
}
73

74
void modify(int u, int l, int r, int k) {
75
    if (l <= tr[u].l && tr[u].r <= r) {
76
        // 注意，直接赋值，否则还得多写一个 query 增大常数时间复杂度还容易错
77
        tr[u].lazy = k;
78
        tr[u].val = k * (tr[u].r - tr[u].l + 1);
79
    }
80
    else {
81
        push_down(u);
82
        int mid = tr[u].l + tr[u].r >> 1;
83
        if (l <= mid) modify(u << 1, l, r, k);
84
        if (r > mid) modify(u << 1 | 1, l, r, k);
85
        push_up(u);
86
    }
87
}
88

89
void modify(int x, int y, int k) {
90
    while (top[x] != top[y]) {
91
        if (dep[top[x]] > dep[top[y]]) swap(x, y);
92
        modify(1, id[top[y]], id[y], k);
93
        y = fa[top[y]];
94
    }
95
    if (dep[x] > dep[y]) swap(x, y);
96
    modify(1, id[x], id[y], k);
97
}
98

99
int query(int u, int l, int r) {
100
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
101
    else {
102
        push_down(u);
103
        int mid = tr[u].l + tr[u].r >> 1;
104
        int res = 0;
105
        if (l <= mid) res += query(u << 1, l, r);
106
        if (r > mid) res += query(u << 1 | 1, l, r);
107
        return res;
108
    }
109
}
110

111
int query(int x, int y) {
112
    int res = 0;
113
    while (top[x] != top[y]) {
114
        if (dep[top[x]] > dep[top[y]]) swap(x, y);
115
        res += query(1, id[top[y]], id[y]);
116
        y = fa[top[y]];
117
    }
118
    if (dep[x] > dep[y]) swap(x, y);
119
    res += query(1, id[x], id[y]);
120
    return res;
121
}
122

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

133
int main() {
134
    int n, m;
135
    scanf("%d", &n);
136
    for (int i = 2; i <= n; ++i) { // 一定要这么写, 后果不堪设想
137
        int t;
138
        scanf("%d", &t);
139
        add(t + 1, i);
140
    }
141
    dep[1] = 1;
142
    dfs(1);
143
    dfs(1, 1);
144
    build(1, 1, n);
145
    scanf("%d", &m);
146
    while (m--) {
147
        string s;
148
        int t;
149
        cin >> s, scanf("%d", &t);
150
        ++t; // 一定要这么写, 后果不堪设想
151
        if (s == "install") {
152
            printf("%d\n", dep[t] - query(1, t));
153
            modify(1, t, 1);
154
        }
155
        else {
156
            printf("%d\n", query(1, id[t], id[t] + cnt[t] - 1));
157
            modify(1, id[t], id[t] + cnt[t] - 1, 0);
158
        }
159
    }
160
    return 0;
161
}

Star's Blog