软件包管理器

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

树链剖分把根到 x 的路径拆成 O(log n) 段连续区间，配合带懒标记的线段树做区间赋值与求和，用段长减和得到安装数、子树区间和得到卸载数。

OJ: roj

题目 ID: 1562

难度:提高

标签:树链剖分线段树树python

创建: 2026-09-30 18:11

更新: 2026-10-07 12:15

前置题目

luogu P1253扶苏的问题B 的线段树 cover 复用了 A 教的「整段覆盖只改摘要和懒标记、进入子树前下传」这一步——整段赋值时直接改 tr[i] 与 tg[i]、下探前把 tg 下推给儿子，只是摘要由区间最大值换成区间和、并去掉了 A 的加法标记；B 的主要新增流程是 A 未教的树链剖分与先序编号。luogu P3870[TJOI2009] 开关B 的 install 段直接复用 A 教的关键观察「整段取反后数量 = len - sum」：把「段长减区间和」当作区间内未安装（0）的个数，再整段赋 1，B 的 main.py 里 cnt += 段长 - cover(...) 与 A 的结算公式同源，B 只是在其上叠加树链剖分与 DFS 序。luogu P2590[ZJOI2008] 树的统计B 的 install 直接复用 A 教的树链剖分拆路径方法，沿链头把根到 x 拆成连续区间逐段赋值，只是把 A 的区间查询换成带懒标记的区间赋值

后置题目

roj 1564「一本通 4.5 练习 4」旅行B 的 path_spans 直接复用 A 教的重链头部跳跃拆路径：每次摘下一段连续的 [pos(head), pos(x)] 区间、再跳到链顶父亲，A 用它逐段置 1，B 用它逐段二分求秩后统计，B 只是把单条根到 x 路径推广为 x→y 并叠加按信仰分堆。shumeng CSP202509D造题计划（上）A 教的关键观察——用树链剖分让根到 x 的路径拆成 O(log n) 段连续区间——正是 B 解法的第一步：B 在 main.cpp 里用同样的链头跳转把路径拆成剖分区间，再叠加「路径补集=相邻区间空隙」的扫描，用区间最小值线段树回答 mex。

形式化题目

给定一棵以 $0$ 为根、共 $n$ 个节点的树：除根外每个节点恰有一个父亲，依赖关系无环。每个节点维护一个布尔状态「是否已安装」，初始全部未安装。支持两类操作，每次操作先输出被改变状态的节点数，再应用操作：

安装 $x$ ：把根到 $x$ 的整条路径上未安装的节点全部置为已安装；
卸载 $x$ ：把 $x$ 的整棵子树中已安装的节点全部置为未安装。

若 $x$ 已安装时执行安装、或 $x$ 未安装时执行卸载，则状态不会改变，输出 $0$ 。

两类操作始终维护同一条性质：已安装集合对祖先封闭——某个节点已安装，则它的全部祖先必然已安装（安装会带上整条祖先链，卸载只删子树、不会波及祖先）。因此「 $x$ 已安装」与「根到 $x$ 的路径全部已安装」是等价说法，卸载一个未安装的节点时它的子树里也必然没有已安装的节点。

样例的依赖树如下（边表示「父依赖子方向」的父子关系，例如 $1$ 依赖 $0$ ）：

graph TD
    0["0"]
    1["1"]
    2["2"]
    3["3"]
    4["4"]
    5["5"]
    6["6"]
    0 --> 1
    0 --> 2
    0 --> 3
    1 --> 4
    1 --> 5
    5 --> 6

按样例依次操作：安装 $5$ 需要装上 $0,1,5$ （输出 $3$ ）；再装 $6$ 只差它自己（输出 $1$ ）；卸载 $1$ 会连带卸掉子树里的 $1,5,6$ （输出 $3$ ）；装 $4$ 只需补上 $1,4$ （输出 $2$ ）；最后卸载 $0$ 卸掉全部已安装的 $0,1,4$ （输出 $3$ ）。

正解

思路

朴素做法：直接模拟。安装 $x$ 沿父指针一路向上逐个检查、逐个置 $1$ ；卸载 $x$ 遍历整棵子树逐个检查、逐个置 $0$ 。每次操作的代价与「被改变状态的节点数」同阶，看起来是均摊的。

瓶颈：真实数据里有深度上万的链，反复「安装深节点 → 卸载根」时，总改动量达到 $1.5 \times 10^8$ ，逐点修改在 Python 下撑不住。这说明瓶颈不在复杂度阶数，而在于逐个节点改状态这件事本身——必须让「把一整段区间置 $0$ / 置 $1$ 」成为一次带懒标记的批量操作，答案也从区间里一次求和得到。

关键观察：两类操作恰好都能翻译成一维区间上的「区间赋值 + 区间求和」，只差一个把树映射成一维下标的方案：

子树是连续区间：对树做先序编号（DFS 序）， $x$ 的子树恰好占据 $[\mathrm{pos}(x),\ \mathrm{pos}(x) + \mathrm{size}(x) - 1]$ 。于是卸载 = 该区间求和（即被卸载个数）后整体赋 $0$ 。
根到 $x$ 的路径拆成 $O(\log n)$ 段连续区间：先做树链剖分——每个节点选子树最大的儿子作重儿子，重儿子串成重链。再按「重儿子优先」的顺序编号，每条重链在编号上连续、子树也仍然连续。安装时从 $x$ 沿链头跳向根，每跳一次处理 $[\mathrm{pos}(\mathrm{head}),\ \mathrm{pos}(x)]$ 一整段，段数等于路径上的轻边数，不超过 $O(\log n)$ 。每段 = 段长 $-$ 区间和（未安装个数）后整体赋 $1$ 。
线段树带懒标记同时支持区间求和与区间赋值，把每段的代价压到 $O(\log n)$ 。

样例树按上述规则编号后的结果（重链为 $0 \to 1 \to 5 \to 6$ ）：

节点	pos	链头	子树区间
0	0	0	$[0, 6]$
1	1	0	$[1, 4]$
5	2	0	$[2, 3]$
6	3	0	$[3, 3]$
4	4	4	$[4, 4]$
2	5	2	$[5, 5]$
3	6	3	$[6, 6]$

表格展示了 pos、链头与子树区间三种下标视角：重链 $0\text{-}1\text{-}5\text{-}6$ 连续占据 $[0,3]$ ，其余节点各自成链；同时每个子树仍是连续区间，例如 $1$ 的子树 $[1,4]$ 正好含 $1,5,6,4$ 。以样例的 install 4 为例：先跳到链头 $4$ 处理 $[4,4]$ （补装 $4$ ），再令 $x = 1$ 跳到链头 $0$ 处理 $[0,1]$ （其中 $0$ 已装、只补 $1$ ），两段合计输出 $2$ 。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 18:20
# update_at: 2026-09-30 18:20

import sys


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    n = int(next(tokens))
    par = [-1] + [int(next(tokens)) for _ in range(n - 1)]  # 1..n-1 号各自依赖的软件包
    q = int(next(tokens))

    # 孩子表 + 先序（祖先先于后代），逆序即为自底向上的求值顺序
    ch: list[list[int]] = [[] for _ in range(n)]
    for v in range(1, n):
        ch[par[v]].append(v)
    order: list[int] = []
    stack = [0]
    while stack:
        v = stack.pop()
        order.append(v)
        stack.extend(ch[v])

    size = [1] * n
    heavy = [-1] * n
    for v in reversed(order):
        for c in ch[v]:
            size[v] += size[c]
            if heavy[v] < 0 or size[c] > size[heavy[v]]:
                heavy[v] = c  # 最重儿子：子树最大的儿子，重链沿它延伸

    # 重链优先的先序压成 pos：重链区间连续、子树区间 [pos, pos+size-1] 也连续
    pos = [0] * n
    head = [0] * n
    seq: list[int] = []
    stack = [0]
    while stack:
        v = stack.pop()
        seq.append(v)
        for c in reversed(ch[v]):
            if c != heavy[v]:
                stack.append(c)  # 轻儿子先压栈，重儿子最后压 = 最先弹出
        if heavy[v] != -1:
            stack.append(heavy[v])
    for i, v in enumerate(seq):
        pos[v] = i
    head[0] = 0
    for v in seq[1:]:
        head[v] = v if heavy[par[v]] != v else head[par[v]]  # 轻儿子自立链头

    # 线段树：区间求和 + 区间赋值，标记 -1 表示该节点没有未下推的赋值
    tr = [0] * (4 * n)
    tg = [-1] * (4 * n)

    def cover(i: int, nl: int, nr: int, l: int, r: int, v: int) -> int:
        """把区间 [l,r] 全部赋值为 v，返回它们修改前的和。"""
        if r < nl or nr < l:
            return 0
        if l <= nl and nr <= r:
            prev = tr[i]
            tr[i] = v * (nr - nl + 1)
            tg[i] = v
            return prev
        mid = (nl + nr) >> 1
        t = tg[i]
        if t != -1:  # 下推标记后才能安全地下探
            tr[i << 1] = t * (mid - nl + 1)
            tr[i << 1 | 1] = t * (nr - mid)
            tg[i << 1] = tg[i << 1 | 1] = t
            tg[i] = -1
        prev = cover(i << 1, nl, mid, l, r, v) + cover(i << 1 | 1, mid + 1, nr, l, r, v)
        tr[i] = tr[i << 1] + tr[i << 1 | 1]
        return prev

    last = n - 1
    out: list[str] = []

    for _ in range(q):
        op = next(tokens)
        x = int(next(tokens))
        if op == b"install":
            # 沿重链跳到根：路径拆成 O(log n) 段连续区间，逐段置 1，
            # 段长减去原有和 = 这段里原来是 0（未安装）的个数
            cnt, v = 0, x
            while True:
                h = head[v]
                lo, hi = pos[h], pos[v]
                cnt += hi - lo + 1 - cover(1, 0, last, lo, hi, 1)
                if h == 0:
                    break
                v = par[h]
            out.append(str(cnt))
        else:
            # 子树在 pos 上是连续区间：置 0 前的和即被卸载的个数
            lo = pos[x]
            out.append(str(cover(1, 0, last, lo, lo + size[x] - 1, 0)))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:26
 * update_at: 2026-10-05 08:26
 */
// 软件包管理器：树链剖分 + 线段树（区间赋值 + 区间求和）
// install x：把根到 x 的路径拆成 O(log n) 段重链区间，每段用 段长-和 数出未安装个数后整体赋 1
// uninstall x：x 的子树在 DFS 序上恰好是连续区间 [pos[x], pos[x]+size[x]-1]，
//              用区间和数出已安装个数后整体赋 0

#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXN = 100005;

int n, qnum;
int fa[MAXN];        // fa[v]：v 的父节点（依赖的软件包）
int son[MAXN];       // son[v]：v 的重儿子（子树最大的儿子），没有则为 -1
int head[MAXN];      // head[v]：v 所在重链的链头
int pos[MAXN];       // pos[v]：v 在重链优先 DFS 序中的下标
int sz[MAXN];        // sz[v]：v 的子树大小
int chhead[MAXN];    // chhead[v]：v 的第一个孩子（孩子表链表头），-1 表示没有孩子
int chnext[MAXN];    // chnext[i]：孩子表中下一条边的下标，与 chhead 配对，节省建 vector
int ord[MAXN];       // 迭代版 DFS 的先序序列，ord[i] = 第 i 个访问的节点
int seq_cnt;

// 线段树：sum 为区间内已安装个数；lazy = -1 表示没有未下推的赋值标记，0/1 表示整段赋值
ll sum[4 * MAXN];
ll lazy[4 * MAXN];   // 标记用 ll，与 sum 同类型相乘，避免强制转换

// 建立孩子表：把 v 挂到 fa[v] 的孩子表头
void add_child(int v) {
    chnext[v] = chhead[fa[v]];
    chhead[fa[v]] = v;
}

// 迭代版 DFS：先序遍历求出 sz、son，顺带保证父亲先于儿子被访问
// 用 ord[] 数组手工模拟栈，避免深链时递归爆栈
void dfs_build() {
    seq_cnt = 0;
    ord[seq_cnt++] = 0;
    // 先序逆序处理即为自底向上：先算完所有孩子，再算父亲
    for (int i = 0; i < seq_cnt; ++i) {
        int v = ord[i];
        for (int c = chhead[v]; c != -1; c = chnext[c]) ord[seq_cnt++] = c;
    }
    // 此时 ord 已经完整，从后往前累加子树大小并挑重儿子
    for (int i = seq_cnt - 1; i >= 0; --i) {
        int v = ord[i];
        sz[v] = 1;
        int best = -1;
        for (int c = chhead[v]; c != -1; c = chnext[c]) {
            sz[v] += sz[c];
            if (best == -1 || sz[c] > sz[best]) best = c;
        }
        son[v] = best;
    }
}

// 重链优先的先序编号：重儿子接着当前链编，轻儿子自立新链
// 每条重链的编号连续，每个子树的编号区间 [pos, pos+sz-1] 也连续
int build_pos_cnt;
void dfs_split() {
    // 数组模拟栈：栈顶指针 tp，元素为待访问节点
    static int stk[MAXN];
    int tp = 0;
    stk[tp++] = 0;
    head[0] = 0;
    while (tp > 0) {
        int v = stk[--tp];
        pos[v] = build_pos_cnt++;
        // 先压轻儿子再压重儿子：重儿子最后压入 = 最先弹出，编号紧接父亲
        for (int c = chhead[v]; c != -1; c = chnext[c]) {
            if (c == son[v]) continue;
            head[c] = c; // 轻儿子自立链头
            stk[tp++] = c;
        }
        if (son[v] != -1) {
            head[son[v]] = head[v]; // 重儿子继承父亲的链头
            stk[tp++] = son[v];
        }
    }
}

// 左右孩子的和上推
void push_up(int i) {
    sum[i] = sum[i * 2] + sum[i * 2 + 1];
}

// 下推懒标记：把整段赋值标记传给两个孩子
void push_down(int i, int nl, int nr) {
    if (lazy[i] == -1) return;
    int mid = (nl + nr) / 2;
    lazy[i * 2] = lazy[i];
    sum[i * 2] = lazy[i] * (mid - nl + 1);
    lazy[i * 2 + 1] = lazy[i];
    sum[i * 2 + 1] = lazy[i] * (nr - mid);
    lazy[i] = -1;
}

void build_tree(int i, int nl, int nr) {
    lazy[i] = -1;
    sum[i] = 0;
    if (nl == nr) return;
    int mid = (nl + nr) / 2;
    build_tree(i * 2, nl, mid);
    build_tree(i * 2 + 1, mid + 1, nr);
}

// 把 [l,r] 整段赋值为 v，返回修改前的区间和（即被改变状态的节点数）
ll cover(int i, int nl, int nr, int l, int r, int v) {
    if (l <= nl && nr <= r) {
        ll before = sum[i];
        lazy[i] = v;
        sum[i] = (ll)v * (nr - nl + 1); // v 是 0/1，乘段长得到区间和
        return before;
    }
    push_down(i, nl, nr);
    int mid = (nl + nr) / 2;
    ll before = 0;
    if (l <= mid) before += cover(i * 2, nl, mid, l, r, v);
    if (r > mid) before += cover(i * 2 + 1, mid + 1, nr, l, r, v);
    push_up(i);
    return before;
}

int main() {
    scanf("%d", &n);
    memset(chhead, -1, sizeof(int) * n);
    fa[0] = -1;
    for (int v = 1; v < n; ++v) {
        scanf("%d", &fa[v]);
        add_child(v);
    }
    dfs_build();
    build_pos_cnt = 0;
    dfs_split();
    build_tree(1, 0, n - 1);

    scanf("%d", &qnum);
    char op[16];
    int x;
    for (int t = 0; t < qnum; ++t) {
        scanf("%s %d", op, &x);
        ll changed;
        if (op[0] == 'i') {
            // 安装：从 x 沿重链跳向根，每跳一段 [pos[head], pos[x]] 赋 1
            changed = 0;
            while (x != -1) {
                int h = head[x];
                // cover 返回修改前的和（已安装数），新增安装数 = 段长 - 和
                ll seg_len = pos[x] - pos[h] + 1;
                changed += seg_len - cover(1, 0, n - 1, pos[h], pos[x], 1);
                x = fa[h];
            }
        } else {
            // 卸载：整棵子树是连续区间 [pos[x], pos[x]+sz[x]-1]，赋 0
            changed = cover(1, 0, n - 1, pos[x], pos[x] + sz[x] - 1, 0);
        }
        printf("%lld\n", changed);
    }
    return 0;
}

复杂度

预处理（求子树大小、重儿子、重链编号）为 $O(n)$ 。每次安装拆成 $O(\log n)$ 段区间赋值，每段在线段树上 $O(\log n)$ ，合计 $O(\log^2 n)$ ；每次卸载只操作一个子树区间，为 $O(\log n)$ 。总复杂度 $O((n + q) \log^2 n)$ ，空间 $O(n)$ 。本仓库 20 组真实数据全部输出一致，最慢一组约 $2\,\mathrm{s}$ （本地 20s 限时）。

总结

把「逐点改状态」换成「区间批量改」是本题的核心：先序编号让子树变成连续区间，树链剖分让根到 $x$ 的路径变成 $O(\log n)$ 段连续区间，最后由带懒标记的线段树统一完成区间求和与区间赋值——安装用「段长 $-$ 和」数出未安装个数，卸载用区间和数出已安装个数。

图示解析

这张图串起本题从朴素模拟到最终做法的推导主线：

text

1
2
3
4
5
6
7逐点模拟（安装走上链、卸载遍历子树）
|- 改动量 = 总状态变化，深链数据下爆炸
`- 换成区间批量操作
   |- 先序编号：子树 = 连续区间 [pos, pos+size-1]
   `- 重链剖分：根到 x 路径 = O(log n) 段连续区间
      `- 线段树懒标记：区间赋值 + 求和
         `- install：段长-和 后置 1；uninstall：求和后置 0

先看第一行暴露的瓶颈，再顺着分支检查两种编号如何把树上操作翻译成一维区间，最后确认线段树如何同时给出答案并完成赋值。

【题目描述】

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

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 $A$ 依赖软件包 $B$ ，那么安装软件包 $A$ 以前，必须先安装软件包 $B$ 。同时，如果想要卸载软件包 $B$ ，则必须卸载软件包 $A$ 。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 $0$ 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 $0$ 号软件包不依赖任何一个软件包。依赖关系不存在环（若有 $m (m≥2)$ 个软件包 $A\_1, A\_2, A\_3, … ,A\_m$ ，其中 $A\_1$ 依赖 $A\_2$ ， $A\_2$ 依赖 $A\_3$ 依赖 $A\_4$ ，……， $A\_{m−1}$ 依赖 $A\_m$ ，而 $A\_m$ 依赖 $A\_1$ ，则称这 $m$ 个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。

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

【输入】

输入的第 $1$ 行包含 $1$ 个正整数 $n$ ，表示软件包的总数。软件包从 $0$ 开始编号。

随后一行包含 $n−1$ 个整数，相邻整数之间用单个空格隔开，分别表示 $1,2,3,…,n−2,n−1$ 号软件包依赖的软件包的编号。

接下来一行包含一个正整数 $q$ ，表示询问的总数。

之后 $q$ 行，每行一个询问。询问分为两种：

$install\\ x$ ：表示安装软件包 $x$

$uninstall\\ x$ ：表示卸载软件包 $x$

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

【输出】

输出包括 $q$ 行。输出文件的第 $i$ 行输出一个整数，为第 $i$ 步操作中改变安装状态的软件包数。

【输入样例】

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

【输出样例】

text

【提示】

样例解释：

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

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

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

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

之后安装 $4$ 号软件包，需要安装 $1,4$ 两个软件包。此时 $0,1,4$ 处在安装状态。

最后，卸载 $0$ 号软件包会卸载所有的软件包。

数据范围与提示：

对于所有数据， $n≤100000, q≤100000$ 。

【来源】

一本通在线评测