文件夹合并

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

用兄弟链表拼接被删除文件夹的子链表，并以 DFS 序差分维护访问路径上的存活文件夹数量。

OJ: shumeng

题目 ID: CSP202403E

难度:提高+/省选-

标签:树链表DFS 序树状数组

日期: 2026-07-31 16:21

形式化题目

文件夹构成一棵根为 $1$ 的树，每个文件夹有若干直接数据。两类操作：

合并文件夹 $x$ ：删除 $x$ 当前的所有直接子文件夹，把这些子文件夹的子文件夹提升为 $x$ 的直接子文件夹，并把被删子文件夹的直接数据累加到 $x$ 上。输出合并后 $x$ 的直接子文件夹数和总数据量。
访问文件夹 $x$ （ $x$ 未被删除）：输出从根到 $x$ 需要经过的存活文件夹个数（含根与 $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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，显式修改父子关系并沿父指针计算深度，只适合小规模对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;

int n, operation_count;
int parent[MAXN];          // 当前的父文件夹
vector<int> child[MAXN];   // 当前每个文件夹的直接子文件夹
long long folder_data[MAXN]; // 当前文件夹直接拥有的数据量
bool alive[MAXN];          // 文件夹是否仍然存在（未被合并删除）

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

    cin >> n >> operation_count;
    for (int i = 2; i <= n; i++) {
        cin >> parent[i];
        child[parent[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) cin >> folder_data[i];
    for (int i = 1; i <= n; i++) alive[i] = true;

    while (operation_count--) {
        int type, node;
        cin >> type >> node;
        if (type == 1) {
            // 合并：删除 node 的所有直接子文件夹，把它们的子文件夹提升上来
            vector<int> old_child = child[node];
            child[node].clear();
            for (int i = 0; i < (int)old_child.size(); i++) {
                int removed = old_child[i];
                folder_data[node] += folder_data[removed];
                alive[removed] = false;
                // 被删子文件夹的子文件夹改为 node 的直接子文件夹
                for (int j = 0; j < (int)child[removed].size(); j++) {
                    int promoted = child[removed][j];
                    parent[promoted] = node;
                    child[node].push_back(promoted);
                }
                child[removed].clear();
            }
            cout << child[node].size() << ' ' << folder_data[node] << '\n';
        } else {
            // 访问：沿父指针向上走，统计路径上存活的文件夹数量
            int count = 1;
            int current = node;
            while (parent[current] != 0) {
                current = parent[current];
                if (alive[current]) count++;
            }
            cout << count << '\n';
        }
    }

    return 0;
}

这个做法每次合并都要移动整棵子树，最坏 $O(n)$ 一次，只适合小数据验证。

主解一：兄弟链表完成合并

给每个文件夹维护一条“当前直接子节点”的双向链表，记录首子 head、尾子 tail 以及每个节点的兄弟前驱 prev_sib 与后继 next_sib。

合并 $x$ 时：

依次从 $x$ 链表头部取出一个子节点 $y$ ；
把 folder_data[y] 累加到 folder_data[x]，删除 $y$ ；
把 $y$ 的整条子链表接到 $x$ 子链表的尾部。

链表拼接是 $O(1)$ 的，不需要逐个移动被提升的节点。每个文件夹至多被删除一次，所以所有 pop 与拼接的总代价是 $O(n)$ 。

主解二：DFS 序差分维护访问层数

删除节点不改变原树的祖先关系，只是让被删的祖先从访问路径中被跳过。于是访问 $x$ 的层数等于原树深度 + 1 - 路径上已删除祖先数。

对原树做一遍 DFS，得到每个节点的子树区间 $[tin, tout]$ 。删除节点 $y$ 时，在树状数组上对区间 $[tin[y], tout[y]]$ 做 $+(-1)$ 。这样 $y$ 的每个后代（在原树中）在查询时都会把这个已删除祖先计入。访问 $x$ 时对 tin[x] 做单点查询，就得到路径上删除祖先数量的相反数，答案即

\text{depth}[x] + 1 + \text{query}(\text{tin}[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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;

int n, operation_count;
vector<int> original_child[MAXN]; // 原树的子节点，用来计算 DFS 序
int parent[MAXN], depth[MAXN], tin[MAXN], tout[MAXN]; // 原树的父、深度与 DFS 子树区间
// 当前树的兄弟链表：head/tail 是首子/尾子，prev_sib/next_sib 是兄弟前驱/后继
int head[MAXN], tail[MAXN], prev_sib[MAXN], next_sib[MAXN];
int child_count[MAXN];   // 当前文件夹的直接子节点数量
long long folder_data[MAXN]; // 当前文件夹直接拥有的数据量
int fenwick[MAXN];       // 树状数组，维护 DFS 序上的区间差分
int timer_count;         // DFS 计时器

// 树状数组：单点加
void bit_add(int pos, int value) {
    for (int i = pos; i <= n; i += i & -i) fenwick[i] += value;
}

// 树状数组：前缀和
int bit_query(int pos) {
    int result = 0;
    for (int i = pos; i > 0; i -= i & -i) result += fenwick[i];
    return result;
}

// 树状数组差分：区间 [left, right] 加 value
void range_add(int left, int right, int value) {
    bit_add(left, value);
    bit_add(right + 1, -value);
}

// 迭代 DFS 计算每个节点的 DFS 子树区间，避免原树是长链时递归栈溢出
void dfs(int root) {
    vector<int> next_child(n + 1, 0); // 记录每个节点已经处理到第几个子节点
    vector<int> stack;
    stack.push_back(root);
    tin[root] = ++timer_count;
    while (!stack.empty()) {
        int current = stack.back();
        if (next_child[current] < (int)original_child[current].size()) {
            int child = original_child[current][next_child[current]];
            next_child[current]++;
            depth[child] = depth[current] + 1;
            tin[child] = ++timer_count;
            stack.push_back(child);
        } else {
            tout[current] = timer_count;
            stack.pop_back();
        }
    }
}

// 从节点 node 的链表头部取走一个子节点并返回
int pop_child(int node) {
    int child = head[node];
    head[node] = next_sib[child];
    if (head[node] == 0) {
        tail[node] = 0;
    } else {
        prev_sib[head[node]] = 0;
    }
    next_sib[child] = 0;
    prev_sib[child] = 0;
    child_count[node]--;
    return child;
}

// 把 source 的整条子链表接到 target 的子链表尾部，并清空 source
void append_children(int target, int source) {
    if (head[source] == 0) return;
    if (tail[target] == 0) {
        head[target] = head[source];
        tail[target] = tail[source];
        prev_sib[head[target]] = 0;
    } else {
        next_sib[tail[target]] = head[source];
        prev_sib[head[source]] = tail[target];
        tail[target] = tail[source];
    }
    child_count[target] += child_count[source];
    head[source] = 0;
    tail[source] = 0;
    child_count[source] = 0;
}

// 合并文件夹 node：删除其当前所有直接子节点，数据并入 node，子链表上提
void merge_folder(int node) {
    int original_count = child_count[node];
    for (int i = 0; i < original_count; i++) {
        int child = pop_child(node);
        folder_data[node] += folder_data[child];
        append_children(node, child);
        // 删除的 child 成为路径上被跳过的祖先，对它的原树后代区间加 -1
        range_add(tin[child], tout[child], -1);
    }
}

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

    cin >> n >> operation_count;
    for (int i = 2; i <= n; i++) {
        cin >> parent[i];
        original_child[parent[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) cin >> folder_data[i];

    dfs(1);

    // 初始时按原父子关系建立兄弟链表
    for (int node = 2; node <= n; node++) {
        int p = parent[node];
        if (head[p] == 0) {
            head[p] = node;
        } else {
            prev_sib[node] = tail[p];
            next_sib[tail[p]] = node;
        }
        tail[p] = node;
        child_count[p]++;
    }

    while (operation_count--) {
        int type, node;
        cin >> type >> node;
        if (type == 1) {
            merge_folder(node);
            cout << child_count[node] << ' ' << folder_data[node] << '\n';
        } else {
            // 当前层数 = 原树深度 + 1，减去路径上已删除的祖先数量
            cout << depth[node] + 1 + bit_query(tin[node]) << '\n';
        }
    }

    return 0;
}

复杂度

设节点数 $n$ 、操作数 $m$ 。

时间：DFS 与初始化 $O(n)$ ；每个文件夹只被从链表中取出一次，合并操作总计 $O(n)$ 次链表操作；每次合并或访问的树状数组操作为 $O(\log n)$ ，总时间复杂度 $O((n + m) \log n)$ 。
空间：各数组均为 $O(n)$ ，空间复杂度 $O(n)$ 。

总结

动态树结构变化题，把问题拆成两半：用兄弟链表维护当前子节点集合，用原树 DFS 序 + 差分树状数组维护“哪些祖先已被删除”。前者让合并变成常数时间的链表拼接，后者把“沿路径数节点”变成一次单点查询，避免了逐个重挂子树的大代价。

题目来自第 33 次 CSP 认证 T5，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 2.0 秒

空间限制： 512 MB

题目描述

新入职西西艾弗岛有限公司的小 C 接替了刚刚升职的小 S 的项目。然而小 C 打开项目工程时，一层层嵌套的文件夹让小 C 感到眼花缭乱。为了精简项目结构，小 C 决定对项目的文件夹进行一些必要的合并。

项目中共有 $n$ 个文件夹。为了方便，我们用 $1$ 至 $n$ 的整数给这 $n$ 个文件夹编号，其中编号为 $1$ 的文件夹为项目的根文件夹，其他每个文件夹都有一个父文件夹，这些文件夹构成了树形结构。除了子文件夹以外，第 $i$ 个文件夹内还直接存储了 $d_i$ 字节的数据。

小 C 进行了若干次文件夹合并操作。每次操作中小 C 会选择一个文件夹 $x_j$ ，将这个文件夹和它的所有子文件夹合并。具体地，小 C 会进行以下操作：遍历 $x_j$ 的子文件夹 $y$ ，将文件夹 $y$ 包含的所有文件夹和文件移动到文件夹 $x_j$ ，然后删除文件夹 $y$ 。所有文件和文件夹的名称是两两不同的，合并过程中不需要考虑文件或文件夹重名的情况。在每一次合并操作后，小 C 需要知道文件夹 $x_j$ 内共有几个文件夹以及多少字节的数据。

例如，考虑以下项目：根文件夹内有文件夹 $2$ 和文件夹 $3$ 以及 $100$ 字节数据，其中文件夹 $2$ 为空文件夹，文件夹 $3$ 内有 $200$ 字节数据和文件夹 $4$ ，文件夹 $4$ 包含 $300$ 字节数据。对根文件夹进行一次合并后，文件夹 $2$ 和文件夹 $3$ 被合并至根文件夹，此时根文件夹下有文件夹 $4$ 以及 $300$ 字节数据，而文件夹 $4$ 下也包含 $300$ 字节数据。

在合并文件夹的过程中，小 C 常常需要访问某个文件夹 $z_j$ 下的文件。此时，小 C 会从根文件夹开始，每次进入当前文件夹的一个子文件夹。小 C 需要知道按照以上过程，获取到文件夹 $z_j$ 下的文件至少需要经过多少个文件夹。

例如，在以上项目中，未对根文件夹进行合并前，访问根文件夹下的文件只需要经过根文件夹一个文件夹，而访问文件夹 $4$ 则需要经过根文件夹以及文件夹 $3$ 和 $4$ 。而对根文件夹进行合并之后，访问文件夹 $4$ 只需要经过根文件夹和文件夹 $4$ 了。

在整个项目中，小 C 一共进行了 $m$ 次文件夹合并以及文件访问操作。你需要帮助小 C 正确维护文件夹之间的关系，并在每次操作后正确回答小 C 需要的数据。

输入格式

从标准输入读入数据。

输入的第一行两个整数 $n,m$ ，分别表示文件夹数量以及操作次数。

第二行 $(n-1)$ 个整数 $f_2,\cdots,f_n$ ，其中 $f_i$ 表示文件夹 $i$ 的父文件夹编号。

第三行 $n$ 个整数 $d_1,d_2,\cdots,d_n$ ，其中 $d_i$ 表示文件夹 $i$ 中数据的存储量。

接下来 $m$ 行第 $j$ 行两个整数，第一个整数 $op_j$ 表示操作类型。若 $op_j = 1$ 则表示一次文件夹合并操作，接下来一个整数 $x_j$ 表示合并的文件夹编号；若 $op_j = 2$ 则表示一次文件访问操作，接下来一个整数 $z_j$ 表示访问的文件夹编号。

输出格式

输出到标准输出。

输出 $m$ 行，第 $j$ 行表示第 $j$ 个操作中小 C 需要的数据：若 $op_j=1$ 则输出两个整数，依次表示文件夹 $x_j$ 的子文件夹数量以及数据的存储量；若 $op_j = 2$ 则输出一个整数表示小 C 获取文件夹 $z_j$ 下的数据最少需要经过的文件夹个数。

input1

1
2
3
4
5
6
7
8
94 6
1 1 3
100 0 200 300
2 1
2 4
1 1
2 4
1 1
1 1

output1

子任务

对于所有测试数据，

$1 \leq n \leq 5 \times 10^{5}, 1 \leq m \leq 3 \times n$
$1 \leq f_i \leq n$ ，输入的文件夹结构构成树形结构
$0 \leq d_i \leq 10^{5}$
$1 \leq x_j, z_j \leq n$ ，每次合并操作中给出的文件夹 $x_j$ 没有被删除，每次文件访问操作中给出的文件夹 $z_j$ 没有被删除。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	$n\le$	特殊性质	分值
1	$500$	无	10
2	$5000$	无	15
3	$10^5$	无	15
4	$5\times 10^5$	A	5
5	$5\times 10^5$	B	5
6	$5\times 10^5$	C	10
7	$5\times 10^5$	D	15
8	$5\times 10^5$	E	10
9	$5\times 10^5$	无	15

特殊性质 A： $f_i = (i-1)$ 。

特殊性质 B： $f_i = 1$ 。

特殊性质 C：在文件夹合并操作中， $x_j = 1$ 。

特殊性质 D： $op_j = 1$ ，即没有文件访问操作。

特殊性质 E： $op_j = 2$ ，即没有文件夹合并操作。

提示

本题输入输出量较大，请采用效率较高的输入输出方式。