[NOI2015] 软件包管理器

GitHub 跳转原题关系图返回列表

把安装与卸载操作转成根到点路径设为 1、子树设为 0，再用树链剖分配合线段树维护区间赋值和区间和。

OJ: luogu

题目 ID: P2146

难度:提高+/省选-

标签:树链剖分线段树dfs序树建模

日期: 2026-06-21 03:03

题意

依赖关系构成一棵以 0 为根的树。

install x：需要把根到 x 的依赖链都安装上
uninstall x：需要把 x 以及所有依赖它的后代一起卸载

每次操作输出实际改变了多少个软件包的安装状态。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;

int n;
int parent_arr[MAXN];
vector<int> children[MAXN];
int installed[MAXN];

int install_package(int x) {
    int changed = 0;
    while (x != -1) {
        if (!installed[x]) {
            installed[x] = 1;
            changed++;
        }
        x = parent_arr[x];
    }
    return changed;
}

int uninstall_package(int x) {
    int changed = 0;
    stack<int> st;
    st.push(x);

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        if (installed[u]) {
            installed[u] = 0;
            changed++;
        }

        for (int v : children[u]) {
            st.push(v);
        }
    }

    return changed;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 这是一个朴素模拟：
    // install 就沿父亲链往上装，uninstall 就把整棵子树暴力扫掉。
    cin >> n;
    parent_arr[0] = -1;
    for (int i = 1; i < n; i++) {
        cin >> parent_arr[i];
        children[parent_arr[i]].push_back(i);
    }

    int q;
    cin >> q;
    while (q--) {
        string op;
        int x;
        cin >> op >> x;
        if (op[0] == 'i') {
            cout << install_package(x) << '\n';
        } else {
            cout << uninstall_package(x) << '\n';
        }
    }

    return 0;
}

brute.cpp 直接模拟：

安装就一路跳父亲到根
卸载就暴力遍历整棵子树

这个思路完全正确，但最坏会退化成每次 $O(n)$ 。

这题最关键的转化是：

install x 本质是把根到 x 的路径整体设为 1
uninstall x 本质是把 x 的子树整体设为 0

于是就变成了一个很标准的树链剖分问题。

树链剖分后：

一条路径会拆成若干个 DFS 序连续区间
一棵子树天然对应一个 DFS 序连续区间

再在线段树中维护每个点当前是否已安装，只需要支持：

区间赋值为 0/1
区间求和

为什么区间和就够？

因为安装状态只有 0/1
区间和就是当前已经安装了多少个软件包

所以：

install x 时，先查询路径和，路径长度减去它，就是新装上的软件包个数
uninstall x 时，先查询子树和，这就是本次会被卸载的个数

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;

int n;
int head[MAXN], to[MAXN], nxt[MAXN], edge_cnt;
int parent_arr[MAXN], depth_arr[MAXN];
int sub_size[MAXN], heavy_son[MAXN];
int top_arr[MAXN], dfn[MAXN], rev_dfn[MAXN], dfs_clock;
int seg_sum[MAXN << 2];
int lazy_tag[MAXN << 2];

void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void build_tree_info() {
    static int order[MAXN];
    static int stk[MAXN];

    int ord_cnt = 0;
    int top = 0;
    stk[++top] = 0;
    parent_arr[0] = -1;
    depth_arr[0] = 1;

    while (top > 0) {
        int u = stk[top--];
        order[++ord_cnt] = u;
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            parent_arr[v] = u;
            depth_arr[v] = depth_arr[u] + 1;
            stk[++top] = v;
        }
    }

    for (int idx = ord_cnt; idx >= 1; idx--) {
        int u = order[idx];
        sub_size[u] = 1;
        heavy_son[u] = -1;
        int best_size = 0;

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            sub_size[u] += sub_size[v];
            if (sub_size[v] > best_size) {
                best_size = sub_size[v];
                heavy_son[u] = v;
            }
        }
    }
}

void build_dfn() {
    static int stk_u[MAXN];
    static int stk_top[MAXN];

    int top = 0;
    stk_u[++top] = 0;
    stk_top[top] = 0;

    while (top > 0) {
        int u = stk_u[top];
        int chain_top = stk_top[top];
        top--;

        while (u != -1) {
            top_arr[u] = chain_top;
            dfn[u] = ++dfs_clock;
            rev_dfn[dfs_clock] = u;

            for (int i = head[u]; i != 0; i = nxt[i]) {
                int v = to[i];
                if (v == heavy_son[u]) {
                    continue;
                }
                stk_u[++top] = v;
                stk_top[top] = v;
            }

            u = heavy_son[u];
        }
    }
}

void build_seg(int u, int l, int r) {
    seg_sum[u] = 0;
    lazy_tag[u] = -1;
    if (l == r) {
        return;
    }

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

void apply_set(int u, int l, int r, int val) {
    seg_sum[u] = (r - l + 1) * val;
    lazy_tag[u] = val;
}

void push_down(int u, int l, int r) {
    if (lazy_tag[u] == -1 || l == r) {
        return;
    }

    int mid = (l + r) >> 1;
    apply_set(u << 1, l, mid, lazy_tag[u]);
    apply_set(u << 1 | 1, mid + 1, r, lazy_tag[u]);
    lazy_tag[u] = -1;
}

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

void range_set(int u, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        apply_set(u, l, r, val);
        return;
    }

    push_down(u, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) {
        range_set(u << 1, l, mid, ql, qr, val);
    }
    if (qr > mid) {
        range_set(u << 1 | 1, mid + 1, r, ql, qr, val);
    }
    push_up(u);
}

int query_sum(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return seg_sum[u];
    }

    push_down(u, l, r);
    int mid = (l + r) >> 1;
    int ans = 0;
    if (ql <= mid) {
        ans += query_sum(u << 1, l, mid, ql, qr);
    }
    if (qr > mid) {
        ans += query_sum(u << 1 | 1, mid + 1, r, ql, qr);
    }
    return ans;
}

int query_path_sum(int u, int v) {
    int ans = 0;
    while (top_arr[u] != top_arr[v]) {
        if (depth_arr[top_arr[u]] < depth_arr[top_arr[v]]) {
            swap(u, v);
        }
        ans += query_sum(1, 1, n, dfn[top_arr[u]], dfn[u]);
        u = parent_arr[top_arr[u]];
    }

    if (depth_arr[u] > depth_arr[v]) {
        swap(u, v);
    }
    ans += query_sum(1, 1, n, dfn[u], dfn[v]);
    return ans;
}

void set_path(int u, int v, int val) {
    while (top_arr[u] != top_arr[v]) {
        if (depth_arr[top_arr[u]] < depth_arr[top_arr[v]]) {
            swap(u, v);
        }
        range_set(1, 1, n, dfn[top_arr[u]], dfn[u], val);
        u = parent_arr[top_arr[u]];
    }

    if (depth_arr[u] > depth_arr[v]) {
        swap(u, v);
    }
    range_set(1, 1, n, dfn[u], dfn[v], val);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        add_edge(p, i);
    }

    build_tree_info();
    build_dfn();
    build_seg(1, 1, n);

    int q;
    cin >> q;
    while (q--) {
        string op;
        int x;
        cin >> op >> x;

        if (op[0] == 'i') {
            // 安装 x，相当于把根到 x 的整条依赖链全部设为 1。
            int installed_before = query_path_sum(0, x);
            int changed = depth_arr[x] - installed_before;
            set_path(0, x, 1);
            cout << changed << '\n';
        } else {
            // 卸载 x，相当于把 x 的整棵子树全部设为 0。
            int l = dfn[x];
            int r = dfn[x] + sub_size[x] - 1;
            int installed_before = query_sum(1, 1, n, l, r);
            range_set(1, 1, n, l, r, 0);
            cout << installed_before << '\n';
        }
    }

    return 0;
}

复杂度

树链剖分预处理是 $O(n)$ 。

每次 install 需要 $O(log^2 n)$ ，每次 uninstall 需要 $O(log n)$ 。

总复杂度可以写成 $O(n + q log^2 n)$ ，空间复杂度是 $O(n)$ 。

总结

这题表面是软件包依赖，实质是树上状态维护。

真正要抓住的是两句话：

安装是“根到点路径设为 1”
卸载是“子树设为 0”

一旦做完这个翻译，后面就是树链剖分加线段树的标准套路。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P2146 [NOI2015] 软件包管理器

题目背景

Linux 用户和 OSX 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu 使用的 apt-get，Fedora/CentOS 使用的 yum，以及 OSX 下可用的 homebrew 都是优秀的软件包管理器。

题目描述

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 $a$ 依赖软件包 $b$ ，那么安装软件包 $a$ 以前，必须先安装软件包 $b$ 。同时，如果想要卸载软件包 $b$ ，则必须卸载软件包 $a$ 。

现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 $0$ 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 $0$ 号软件包不依赖任何一个软件包。且依赖关系不存在环（即不会存在 $m$ 个软件包 $a_1,a_2, \dots , a_m$ ，对于 $i<m$ ， $a_i$ 依赖 $a_{i+1}$ ，而 $a_m$ 依赖 $a_1$ 的情况）。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。

注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 $0$ 。

输入格式

第一行一个正整数 $n$ ，表示软件包个数，从 $0$ 开始编号。
第二行有 $n-1$ 个整数，第 $i$ 个表示 $i$ 号软件包依赖的软件包编号。
然后一行一个正整数 $q$ ，表示操作个数，格式如下：

install x 表示安装 $x$ 号软件包
uninstall x 表示卸载 $x$ 号软件包

一开始所有软件包都是未安装的。

对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。

输出格式

输出 $q$ 行，每行一个整数，表示每次询问的答案。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
87
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

输出 #1

text

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7
8
9
10
11
12
1310
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

输出 #2

text

说明/提示

一开始所有软件包都处于未安装状态。

安装 $5$ 号软件包，需要安装 $0,1,5$ 三个软件包。

之后安装 $6$ 号软件包，只需要安装 $6$ 号软件包。此时安装了 $0,1,5,6$ 四个软件包。

卸载 $1$ 号软件包需要卸载 $1,5,6$ 三个软件包。此时只有 $0$ 号软件包还处于安装状态。

之后安装 $4$ 号软件包，需要安装 $1,4$ 两个软件包。此时 $0,1,4$ 处在安装状态。最后，卸载 $0$ 号软件包会卸载所有的软件包。

【数据范围】

::cute-table{tuack}

测试点编号	$n$ 的规模	$q$ 的规模	备注
$1$	${n = 5{,}000}$	${q = 5{,}000}$
$2$	^	^	^
$3$	${n = 100{,}000}$	${q = 100{,}000}$	数据不包含卸载操作
$4$	^	^	^
$5$	${n = 100{,}000}$	${q = 100{,}000}$	编号为 $i$ 的软件包所依赖的软件包编号在 $[0,i - 1]$ 内均匀随机，每次执行操作的软件包编号在 $[0,n-1]$ 内均匀随机
$6$	^	^	^
$7$	^	^	^
$8$	^	^	^
$9$	${n = 100{,}000}$	${q = 100{,}000}$
$10$	^	^	^
$11$	^	^	^
$12$	^	^	^
$13$	^	^	^
$14$	^	^	^
$15$	^	^	^
$16$	^	^	^
$17$	^	^	^
$18$	^	^	^
$19$	^	^	^
$20$	^	^	^

[NOI2015] 软件包管理器

目录

题意

思路

代码

复杂度

总结

一图流解析