1006E Military Problem 展示了怎样用一次 DFS 把子树拍平成连续区间。本文把镜头拉回 DFS 本身，用三道题逐层增加状态：115A 只需要知道节点深度，580C 要把“当前连续有猫数”沿路径传下去，1336A 则要在返回阶段汇总子树大小，再把统计量交给贪心。

三题放在一起的意义，是看清 DFS 并不等于一段固定模板。真正需要设计的是：进入节点时已经知道什么，离开节点时要带回什么，以及哪些信息只属于当前路径。

1. 三道题的官方信息

以下元数据于 2026-09-14 通过 Codeforces 官方题目页核对。

题目 难度 官方标签 约束 本文训练点
115A · Party 900 dfs and similar、graphs、trees 1≤n≤2000，管理关系无环 深度与森林
580C · Kefa and Park 1500 dfs and similar、graphs、trees 2≤n≤10^5，1≤m≤n 路径状态与剪枝
1336A · Linova and Kingdom 1600 dfs and similar、dp、greedy、sortings、trees 2≤n≤2×10^5，1≤k<n 深度、子树大小与贪心

题目规模逐步增大，第三题达到二十万个节点。后两题的完整实现都使用显式栈，避免一条长链把 C++ 调用栈压满。

2. 第一题：115A Party，把分组数变成最大深度

2.1 题目到底在限制什么

公司有 n 名员工。每人没有直属上司，或恰有一名直属上司；管理关系保证无环，所以整体是一片有根森林。要把所有人分组，同组中不能出现“某人是另一人的直接或间接上司”，求最少组数。

朴素想法可能是从第一名员工开始，逐个寻找当前能放的组。但“放进哪个组”会受先前选择影响，模拟过程掩盖了真正的不变量：上下级冲突只发生在同一条祖先链上。

定义根员工的深度为 1，其他员工的深度为直属上司深度加 1。答案就是整片森林的最大深度 H。

2.2 为什么答案恰好是 H

先看下界。取一条长度为 H 的最长管理链，链上任意两人都有上下级关系，因此这 H 人必须分到不同组，答案不可能少于 H。

再看上界。把所有深度相同的人放进同一组。若一个人是另一个人的上司，他一定更接近树根，深度严格更小；所以同深度的两人绝不会构成上下级。用深度 1 到 H 建立 H 组一定合法。

上下界相等，最少组数就是最大深度。这比尝试构造各种分组顺序更直接。

2.3 手工演算

官方样例的直属上司依次是 -1, 1, 2, 1, -1：

员工 直属上司 深度 可放入的组
1 无 1 1
2 1 2 2
3 2 3 3
4 1 2 2
5 无 1 1

最长链是 1→2→3，需要 3 组；员工 2 与 4 深度相同，可以同组，员工 1 与 5 也可以同组。

2.4 完整 C++17 实现

这里用带记忆化的 depthOf 沿父指针向上计算深度。每个节点的深度只会真正求一次。

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
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

using namespace std;

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

    int n;
    cin >> n;

    vector<int> parent(n + 1);
    for (int employee = 1; employee <= n; ++employee) {
        cin >> parent[employee];
    }

    vector<int> depth(n + 1, 0);
    function<int(int)> depthOf = [&](int employee) -> int {
        if (depth[employee] != 0) return depth[employee];
        if (parent[employee] == -1) return depth[employee] = 1;
        return depth[employee] = depthOf(parent[employee]) + 1;
    };

    int answer = 0;
    for (int employee = 1; employee <= n; ++employee) {
        answer = max(answer, depthOf(employee));
    }
    cout << answer << '\n';
}

时间复杂度为 O(n)，空间复杂度为 O(n)。本题深度上限只有 2000，递归记忆化足够安全；若约束扩大到二十万，可以改成显式栈或按入度从根向下遍历。

3. 第二题：580C Kefa and Park，把状态带在当前路径上

3.1 “有几只猫”为什么不够

公园是一棵以 1 为根的树，叶子上有餐厅。每个节点标记是否有猫；若从根到餐厅的路径上出现超过 m 个连续有猫节点，这家餐厅就不能去。目标是统计可达餐厅数。

总猫数不是有效状态。例如两条长度相同的路径都经过三只有猫节点：

1
2
1 1 1 0    最长连续段是 3
1 0 1 1    最长连续段是 2

当 m=2 时，前者非法，后者合法。到达节点 u 时，未来真正关心的是“以 u 结尾的连续有猫段有多长”，记为 consecutive[u]。

3.2 状态转移与剪枝

从父节点 u 走到孩子 v：

1
2
若 v 有猫：next = consecutive[u] + 1
若 v 没猫：next = 0

若 next>m，可以直接剪掉 v 的整棵子树。原因不是“后面不可能再遇到无猫节点”，而是当前根到 v 的路径已经包含一个过长连续段；后面即使清零，也无法抹掉已经发生的违规片段。

3.3 手工演算

考虑路径 1→2→4→7，猫标记为 1,1,0,1，限制 m=2：

到达节点 是否有猫 更新前连续数 更新后连续数 处理
1 1 0 1 继续
2 1 1 2 继续，仍等于上限
4 0 2 0 清零
7 1 0 1 若为叶子，计入答案

若节点 4 也有猫，到达它时连续数会变为 3，整条分支立即被剪掉。

3.4 正确性证明

路径状态不变量： 栈中状态 (u,parent,c) 被处理时，c 等于根到 u 路径末尾的连续有猫节点数。根节点由 0 按自身标记更新，结论成立；从父到子时，有猫便在末尾追加 1，无猫便让末尾连续段归零，所以不变量归纳成立。

若 c>m，根到 u 已经存在非法连续段，任何到 u 后代的路径都以这段前缀开头，因此剪枝不会漏掉合法餐厅。若未被剪枝且 u 没有除父节点外的邻居，u 正是有根树的叶子；依据不变量，它的完整路径满足限制，应且只应计数一次。

3.5 完整 C++17 实现

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
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<int> hasCat(n + 1);
    for (int node = 1; node <= n; ++node) cin >> hasCat[node];

    vector<vector<int>> graph(n + 1);
    for (int edge = 1; edge < n; ++edge) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<tuple<int, int, int>> stack;
    stack.emplace_back(1, 0, 0);
    int answer = 0;

    while (!stack.empty()) {
        auto [node, parent, previous] = stack.back();
        stack.pop_back();

        int consecutive = hasCat[node] ? previous + 1 : 0;
        if (consecutive > m) continue;

        bool isLeaf = true;
        for (int next : graph[node]) {
            if (next == parent) continue;
            isLeaf = false;
            stack.emplace_back(next, node, consecutive);
        }
        if (isLeaf) ++answer;
    }

    cout << answer << '\n';
}

每个节点与每条边只处理常数次，时间复杂度 O(n)，邻接表和显式栈占 O(n) 空间。

4. 第三题：1336A Linova and Kingdom，让子树统计进入贪心

4.1 题目中的两种角色

王国是一棵以 1 为首都的树。恰好选择 k 个工业城市，其余城市发展旅游；每个工业城市派使者沿唯一路径前往首都，使者经过多少个旅游城市，就获得多少幸福值。求所有使者幸福值之和的最大值。

只按深度选最深的 k 个点似乎合理，因为起点越深，路径越长。但若把一个靠近根、拥有大量后代的城市设为工业城市，它会从许多后代使者的旅游路径中消失。深度描述“自己能走多远”，子树大小描述“自己会影响多少后代”，两者必须同时计算。

4.2 先证明旅游城市向根闭合

存在一种最优方案满足：若非根节点 u 是旅游城市，它的父节点也一定是旅游城市。

若 u 是旅游城市而父节点 p 是工业城市，交换两者角色：

  • 原来从 p 出发的使者取消；
  • 新增从 u 出发的使者，它会先经过现在变成旅游城市的 p；
  • 其他工业后代原本经过旅游城市 u，交换后改为经过旅游城市 p，数量不减少；
  • 树外路径不受影响。

因此交换不会让总幸福值变小。重复交换后，旅游城市集合可以整理成“选择一个节点，就同时选择它的所有祖先”的形状。

4.3 每个旅游城市的固定贡献

设：

  • depth[u] 是根到 u 的边数，根深度为 0；
  • subtreeSize[u] 是包含 u 的子树节点数。

若暂时统计每个旅游城市 u 对幸福值的贡献，它能服务子树中的 subtreeSize[u]-1 个真后代。这里还把旅游后代也算进去了；由于旅游集合向根闭合，每个旅游后代 v 的所有 depth[v] 个祖先也都是旅游城市。把这些“没有使者的旅游后代”造成的多算，按后代逐一扣回，得到恒等式：

1
总幸福值 = Σ[(subtreeSize[u] - 1) - depth[u]]，其中 u 遍历旅游城市

所以旅游贡献为：

1
gain[u] = (subtreeSize[u] - 1) - depth[u]

选择最大的 n-k 个贡献即可。这个排序还会自动满足向根闭合：对父子边 p→u，有

1
gain[p] - gain[u] = subtreeSize[p] - subtreeSize[u] + 1 > 0

父节点贡献严格大于孩子，因此只要孩子进入前 n-k 名，父节点一定更早进入。

4.4 官方第一组样例的贡献表

样例中 n=7,k=4，所以选择 3 个旅游城市。树边为 1-2,1-3,1-4,3-5,3-6,4-7。

城市 深度 子树大小 旅游贡献 size-1-depth 排序结果
1 0 7 6 选旅游
2 1 1 -1 选工业
3 1 3 1 选旅游
4 1 2 0 选旅游
5 2 1 -2 选工业
6 2 1 -2 选工业
7 2 1 -2 选工业

前三个贡献之和为 6+1+0=7。对应工业城市可以是 2,5,6,7，四名使者的幸福值分别为 1,2,2,2，总和正好为 7。

4.5 完整 C++17 实现

先用显式栈生成父节点在孩子之前的 order，再逆序累加子树大小。gain 及答案使用 long long：链上深度之和可达到约 2×10^10。

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
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

    int n, k;
    cin >> n >> k;

    vector<vector<int>> graph(n + 1);
    for (int edge = 1; edge < n; ++edge) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<int> parent(n + 1, 0);
    vector<int> depth(n + 1, 0);
    vector<int> order;
    order.reserve(n);
    vector<int> stack{1};

    while (!stack.empty()) {
        int node = stack.back();
        stack.pop_back();
        order.push_back(node);
        for (int next : graph[node]) {
            if (next == parent[node]) continue;
            parent[next] = node;
            depth[next] = depth[node] + 1;
            stack.push_back(next);
        }
    }

    vector<int> subtreeSize(n + 1, 1);
    for (int index = n - 1; index > 0; --index) {
        int node = order[index];
        subtreeSize[parent[node]] += subtreeSize[node];
    }

    vector<long long> gain;
    gain.reserve(n);
    for (int node = 1; node <= n; ++node) {
        gain.push_back(static_cast<long long>(subtreeSize[node] - 1) - depth[node]);
    }
    sort(gain.rbegin(), gain.rend());

    long long answer = 0;
    for (int index = 0; index < n - k; ++index) {
        answer += gain[index];
    }
    cout << answer << '\n';
}

两次遍历为 O(n)，排序为 O(n log n)，总空间复杂度 O(n)。

4.6 正确性证明

引理一： 存在旅游集合向根闭合的最优方案。上面的父子角色交换不减少任一相关使者的幸福值，反复交换即可得到这种方案。

引理二： 对任一向根闭合的旅游集合，总幸福值等于所有旅游城市 gain[u] 之和。subtreeSize[u]-1 先计算旅游城市 u 对全部真后代的潜在服务；每个旅游后代 v 没有使者，却会在其 depth[v] 个旅游祖先处各被多算一次，扣除全部 depth[v] 后恰好只保留工业后代与旅游祖先之间的配对。

引理三： 贡献最大的任意前 n-k 个节点向根闭合。每条父子边上父亲贡献严格大于孩子，所以孩子入选时其全部祖先必已入选。

定理： 排序取前 n-k 个贡献得到最大幸福值。由引理三，这个集合是合法的根闭合旅游集合；在所有大小为 n-k 的节点集合中，前 n-k 个数之和最大。结合引理一与引理二，它至少达到某个最优合法集合的贡献和，因此就是全局最优值。

5. 三题放在一起复盘

题目 进入节点时携带 离开节点时汇总 决策发生在哪里
115A 父节点深度 无 取全局最大深度
580C 当前路径末尾的连续猫数 无 超限剪枝、叶子计数
1336A 父节点与深度 子树大小 对固定贡献排序

常见错误清单

场景 错误做法 正确检查
115A 有多个根 只从一个根出发 把输入看成森林，对每个节点求深度
115A 分组 直接贪心塞组 先证明答案等于最大深度
580C 遇到无猫点 连续数保持不变 必须清零
580C 判断叶子 无向图中只看“未访问”标记 判断是否存在除父节点外的孩子
580C 已经超限 等后面无猫点再恢复 当前非法前缀会保留在所有后代路径中
1336A 只看深度 忽略节点对后代路径的影响 同时计算 depth 与 subtreeSize
1336A 把 k 用反 取 k 个旅游城市 题目规定 k 个工业城市，因此旅游数是 n-k
1336A 使用 int 累加 长链上溢出 贡献与答案使用 long long

6. 独立验证怎样做

tests/verify-tree-dfs-three-article.cjs 会分别提取三段 C++17 程序，以 -Wall -Wextra -pedantic 编译并要求零警告。验证器没有复用文章公式：

  • 115A 沿每个节点的父指针直接数祖先链长度；
  • 580C 枚举每个叶子的完整根路径，再扫描最长连续有猫段；
  • 1336A 在小树上枚举所有恰含 k 个工业城市的集合，逐名使者走到首都计算幸福值。

测试还覆盖官方样例、随机森林、随机树、根有猫、连续段恰等于上限、链与星形树，以及十万至二十万个节点的大输入。第三题的枚举对拍尤其重要，因为它能同时发现“k 的角色用反”“深度差一”和贡献符号写反三类问题。

学完这组三题，再回看 1006E 的 DFS 序与子树区间，会更容易分辨树上信息的三个方向：沿根到点的路径向下传、从子树向上收，以及把访问过程保存为数组供后续查询。