510C Fox And Names 把先后约束变成有向图，再寻找满足约束的线性顺序。Codeforces 1006E 也要构造顺序，但输入已经是一棵以 1 为根的树：我们需要固定孩子访问次序，把一次 DFS 的结果保存下来，回答任意子树里的第 k 个访问点。

关键不在于把 DFS 写出来，而在于证明：一棵子树在先序 DFS 序列中一定占据连续区间。 有了这个性质，最多二十万次查询都只需一次边界判断和一次数组访问。

1. 官方信息与约束

1006E · Military Problem 官方题目 于 2026-09-12 核对：难度 1600，标签为 dfs and similar、graphs、trees，时间限制 3 秒，内存限制 256 MB。

题目给出 n 个点的有根树，根为 1；对每个 i=2..n 给出父节点 p[i]，且 p[i]<i。传播命令时使用 DFS，同一节点的孩子按编号从小到大访问。每次查询 (u,k) 要求从 u 开始传播时第 k 个收到命令的节点；子树不足 k 个点则输出 -1。

官方约束 对设计的直接影响
2≤n≤2×10^5 递归 DFS 可能压满系统调用栈
1≤q≤2×10^5 不能为每次查询重新遍历子树
p[i]<i 按 i=2..n 加入孩子时，孩子表天然递增
1≤u,k≤n 下标和子树大小使用 int 足够

2. 为什么逐次 DFS 不够

最直接的方法是收到查询 (u,k) 后，从 u 开始按规则做 DFS，走到第 k 个点就停止。一次查询最坏访问整棵树，复杂度 O(n)；若树是一条链，q 次查询就会达到 O(nq)，在上限处约为 4×10^10 次操作。

所有查询的访问规则完全相同，只是起点不同。重复计算的部分可以共享：先从根 1 做一次完整先序 DFS，把访问顺序写入数组 order。

3. 三个数组分别表示什么

  • order[pos]：全局 DFS 中第 pos 个访问的节点，位置从 0 开始；
  • tin[u]：节点 u 在 order 中的位置；
  • size[u]：以 u 为根的子树节点数，包含 u 自己。

于是 u 的子树区间为：

1
[tin[u], tin[u] + size[u] - 1]

查询里的 k 从 1 开始，所以答案位置是 tin[u]+k-1。只有当 k≤size[u] 时，这个位置仍在 u 的子树区间内。

手工演算

以官方样例的父节点序列 1 1 1 3 5 3 5 7 为例，树边为 1→2,3,4、3→5,7、5→6,8、7→9。

order 位置 0 1 2 3 4 5 6 7 8
节点 1 2 3 5 6 8 7 9 4
节点 u tin[u] size[u] 对应区间 区间内容
1 0 9 [0,8] 全部节点
3 2 6 [2,7] 3,5,6,8,7,9
5 3 3 [3,5] 5,6,8
7 6 2 [6,7] 7,9
9 7 1 [7,7] 9

例如查询 (3,4)：4≤size[3]=6，目标下标为 tin[3]+4-1=5，所以答案是 order[5]=8。查询 (7,3) 越过了大小为 2 的子树，答案为 -1。

4. 子树为什么是连续区间

先序 DFS 进入 u 时立刻记录 u，然后完整处理第一个孩子的子树，再处理第二个孩子的子树，直到所有孩子结束，才返回 u 的父节点。

因此，从记录 u 的那一刻到离开 u 之前，算法只能访问 u 或它的后代；它不会中途跑到 u 的兄弟节点。反过来，u 的每个后代都会在离开 u 前恰好访问一次。所以这段连续位置包含且只包含 u 的整棵子树，长度正好是 size[u]。

孩子按什么顺序访问，只会改变区间内部的排列，不会破坏子树连续性。本题额外要求编号较小的孩子优先，所以实现还必须精确保留这个次序。

5. 迭代 DFS 怎样保持递增访问

递归写法会自然按 children[u] 的先后顺序深入，但一条含二十万个点的链可能让程序栈溢出。本文改用显式栈。

栈是后进先出。若想先访问较小编号的孩子，就应把孩子按从大到小压栈：最后压入的最小孩子会最先弹出。输入按节点编号递增给出父亲，因此直接 push_back(i) 后，每个孩子表已经升序，无需额外排序。

得到 order 后，先令所有 size[u]=1，再逆序扫描 order。孩子一定晚于父亲进入先序数组，所以逆序时孩子大小已经完整，可以累加到父亲：

1
size[parent[u]] += size[u]

6. 正确性证明

引理一：迭代算法生成题目规定的 DFS 先序

访问节点 u 时，算法把其孩子按编号从大到小压入栈。由于栈后进先出，最小编号孩子最先弹出；这个孩子的全部后代又会压在其他兄弟之上，因此其子树会先完整处理。逐层应用同样规则，所得顺序与“总选最小未访问孩子”的 DFS 相同。

引理二：size[u] 等于 u 的子树节点数

初始化的 1 计入 u 自己。逆序扫描时，任意真后代都比祖先更早处理；每个非根节点的累计大小只加给唯一父亲一次。于是 u 最终得到自己加上所有孩子子树的大小，恰为整棵子树的节点数。

引理三：区间公式准确描述 u 的子树

由先序 DFS 的控制过程，进入 u 后会连续访问完所有后代才离开，期间不访问子树外节点。结合引理二，这段从 tin[u] 开始、长度为 size[u] 的区间包含且只包含 u 的子树。

定理：每次查询输出正确答案

若 k>size[u]，子树内不足 k 个点，输出 -1 正确。否则依据引理三，子树访问序列正是全局 order 从 tin[u] 开始的连续片段，其第 k 项下标为 tin[u]+k-1，算法返回的节点正是题目要求的答案。

7. 完整 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
47
48
49
50
51
52
#include <iostream>
#include <vector>

using namespace std;

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

    int n, q;
    cin >> n >> q;

    vector<int> parent(n + 1, 0);
    vector<vector<int>> children(n + 1);
    for (int node = 2; node <= n; ++node) {
        cin >> parent[node];
        children[parent[node]].push_back(node);
    }

    vector<int> order;
    order.reserve(n);
    vector<int> tin(n + 1);
    vector<int> stack{1};

    while (!stack.empty()) {
        int node = stack.back();
        stack.pop_back();

        tin[node] = static_cast<int>(order.size());
        order.push_back(node);

        for (int i = static_cast<int>(children[node].size()) - 1; i >= 0; --i) {
            stack.push_back(children[node][i]);
        }
    }

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

    while (q--) {
        int u, k;
        cin >> u >> k;
        if (k > subtreeSize[u]) {
            cout << -1 << '\n';
        } else {
            cout << order[tin[u] + k - 1] << '\n';
        }
    }
}

建树、DFS 和逆序累计各为 O(n)，每次查询 O(1)，总时间 O(n+q)；邻接表和三个辅助数组占 O(n) 空间。

8. 边界与错误清单

场景 正确处理 常见错误
k=1 答案永远是 u 忘记查询从 1 开始
k=size[u] 返回区间最后一个点 把合法条件写成严格小于
叶子节点 size[u]=1 初始化为 0 后漏算自身
星形树 根的孩子按编号递增 正序压栈导致访问顺序反转
长链 显式栈保持 O(n) 空间 递归深度达到二十万
逆序累计 跳过根，累加到唯一父亲 把根累加到虚构节点 0
多次查询 只读预处理数组 每次重新跑 DFS

9. 怎样独立验证

tests/verify-military-problem-article.cjs 会提取本文唯一的 C++ 代码块，以 -std=c++17 -Wall -Wextra -pedantic 编译并要求零警告。参考程序在小树上使用递归 DFS 直接生成每个查询起点的局部传播序列，不使用本文的子树区间公式，再与文章程序逐项比较。

测试覆盖官方样例、链、星形树、分叉树、固定种子随机树，以及含二十万个节点的深链。最后一组专门确认迭代实现不会依赖系统递归栈。

这题提供了树算法里很常用的桥梁：树擅长表达祖先和子树关系，数组擅长处理区间与查询；DFS 进入顺序把两种结构连接起来。继续学习树上差分、树状数组或线段树时，“把子树拍平成区间”还会反复出现。