Moe's CF Life

Appearance

E. Military Problem - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 498 (Div. 3) 标签: dfs and similar, graphs, trees 难度: *1600

题目大意喵~ ​

在一个军队里，有 n 个军官，形成了一棵以1号军官（总司令）为根的树状指挥系统。每个军官（除了总司令）都有且仅有一个直接上级。

现在，我们需要处理 q 个独立的查询。每个查询会给出两个数字 (u, k)，表示军官 u 开始下达命令。命令的传播方式是一种特殊的深度优先搜索（DFS）：

  1. 一个军官 a 会向他的直接下属（也就是树中的孩子节点）传达命令。
  2. 如果有多个直接下属，他会选择编号最小且还未接收到命令的下属。
  3. 将命令传给选中的下属 b后，b 会立即用同样的方式向自己的下属传达命令。
  4. 当 b 和他整个下属体系都接收完命令后，a 才会回头选择下一个编号最小的、未接收命令的直接下属。
  5. 当 a 的所有直接下属都接收完命令，a 的传达过程就结束了。

对于每个查询 (u, k)，我们需要找出如果从军官 u 开始传达命令，第 k 个接收到命令的军官是谁。如果 u 的下属（包括他自己）总数少于 k，就输出 -1。

简单来说，就是求从节点 u 开始、并按子节点小编号优先的规则进行DFS，访问到的第 k 个节点是谁，的说。

解题思路，听我分析喵！ ​

一看到这种要在树上反复查询的问题，而且查询次数还不少（q 高达 2e5），我们的第一反应就不能是每次查询都老老实实跑一遍DFS，那样肯定会超时（Time Limit Exceeded）的啦，会变成一只慢吞吞的小懒猫！(>ω<)

正确的姿势是预处理！我们可以利用DFS的一些神奇性质，提前把一些信息算好，这样每次查询就能以 O(1) 的飞快速度得到答案，喵~。

这里的核心思想是 DFS序。

想象一下，我们不从某个特定的 u 开始，而是从总司令，也就是 1号节点 开始，按照题目规定的“子节点小编号优先”的规则进行一次全局DFS。在这次DFS的过程中，我们可以记录下所有节点被访问到的顺序，把它们放进一个大大的列表里，我们叫它 dfs_order 吧！

同时，我们还需要两个小本本（数组）来记录每个节点 v 的信息：

  1. time_in[v]：节点 v 第一次被访问到的“时间点”（也就是它在 dfs_order 列表里的下标）。
  2. subtree_size[v]：以节点 v 为根的子树里，总共有多少个节点（包括 v 自己）。

有了这些预处理好的信息，奇迹就要发生啦！

当我们要查询 (u, k) 时：

  • 从 u 开始的命令传播，只会影响到 u 和他手下的兵，也就是以 u 为根的子树。
  • 这个传播顺序，其实就是我们全局DFS dfs_order 中，从 u 所在位置开始的一段连续子序列！
  • 这段子序列的长度，正好就是 u 的子树大小 subtree_size[u]。

所以，对于查询 (u, k)：

  1. 我们先检查 k 是否大于 u 的子树大小 subtree_size[u]。如果 k 太大了，说明 u 的手下没那么多人，根本找不到第 k 个，就只好输出 -1 啦。
  2. 如果 k 是有效的，那么从 u 开始的第 k 个被访问的节点，就对应着全局 dfs_order 列表里，从 u 的位置（time_in[u]）开始，再往后数 k-1 个位置的那个节点。它的下标就是 time_in[u] + k - 1。

所以，答案就是 dfs_order[time_in[u] + k - 1]！是不是超级简单，喵~？

等等，subtree_size[v] 怎么算呢？ 这里有个小技巧！在DFS时，我们不仅记录进入节点的时间 time_in，也记录完成该节点所有子树访问后“离开”的时间 time_out。那么，以 v 为根的子树的所有节点，在 dfs_order 中就占据了从 time_in[v] 到 time_out[v] 的所有位置。所以，子树大小就是 time_out[v] - time_in[v] + 1！

总结一下我们的完美计划：

  1. 建树：根据输入的上级关系，建立一个邻接表来表示这棵树。
  2. 排序：对于每个节点的子节点列表，都按编号从小到大排个序。这是为了满足题目要求的DFS规则。
  3. 全局DFS：从根节点1开始进行一次DFS。
    • 用一个计时器 timer，从0开始。
    • 当我们第一次访问节点 u 时，记录 time_in[u] = timer，并将 u 存入 dfs_order[timer]，然后 timer++。
    • 当我们访问完 u 的所有子树，准备回溯时，记录 time_out[u] = timer - 1。
  4. 回答查询：对于每个 (u, k)，计算子树大小 sz = time_out[u] - time_in[u] + 1。如果 k > sz，输出 -1；否则，输出 dfs_order[time_in[u] + k - 1]。

这样，预处理是 O(N)，每次查询是 O(1)，总的来说就非常高效啦！

代码实现，看这里喵！ ​

cpp
// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int main() {
    // 加速输入输出，让程序跑得像风一样快，喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    // 用一个邻接表来存放这棵树的结构，children[i] 存储了 i 的所有直接下属
    vector<vector<int>> children(n + 1);
    for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        children[p].push_back(i);
    }

    // 关键一步！题目要求按小编号优先访问，所以要对每个节点的子节点列表排序
    for (int i = 1; i <= n; i++) {
        sort(children[i].begin(), children[i].end());
    }

    // --- 预处理阶段开始 ---

    // dfs_order: 存储全局DFS的访问顺序
    vector<int> dfs_order(n);
    // time_in[u]: 节点u在dfs_order中的首次出现位置（时间戳）
    vector<int> time_in(n + 1, -1);
    // time_out[u]: 节点u的子树在dfs_order中的结束位置（时间戳）
    vector<int> time_out(n + 1, -1);
    // next_index[u]: 辅助迭代DFS，记录u的下一个要访问的子节点索引
    vector<int> next_index(n + 1, 0);

    // 用一个栈来实现非递归的DFS，这样就不会因为树太深而爆栈啦！
    stack<int> st;
    st.push(1); // 从总司令1号开始
    int timer = 0; // 全局计时器

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

        // 如果是第一次访问这个节点
        if (time_in[u] == -1) {
            time_in[u] = timer;      // 记录进入时间
            dfs_order[timer] = u;    // 记录到DFS序中
            timer++;
        }

        // 检查是否还有未访问的子节点
        if (next_index[u] < children[u].size()) {
            int v = children[u][next_index[u]]; // 获取下一个子节点
            next_index[u]++;                    // 更新索引，下次访问再下一个
            st.push(v);                         // 将子节点压入栈中，进行深度探索
        } else {
            // 所有子节点都访问完了，是时候离开这个节点了
            time_out[u] = timer - 1; // 记录离开时间
            st.pop();                // 从栈中弹出
        }
    }

    // --- 查询阶段开始 ---
    while (q--) {
        int u, k;
        cin >> u >> k;
        
        // 子树的大小就是出栈时间 - 入栈时间 + 1
        int subtree_size = time_out[u] - time_in[u] + 1;

        if (k > subtree_size) {
            // k 太大了，超出了子树的范围
            cout << -1 << '\n';
        } else {
            // 计算在全局dfs_order中的准确位置
            int pos = time_in[u] + k - 1;
            cout << dfs_order[pos] << '\n';
        }
    }

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(N log N + Q) 的说。
    • 建树是 O(N)。
    • 对所有子节点列表进行排序，在最坏情况下（比如一条链），每个节点只有一个孩子，总排序时间是 O(N)。在最好情况下（比如一个星形图），根节点有 N-1 个孩子，排序时间是 O(N log N)。总的来说，所有节点度数之和是 2(N-1)，所以排序的总复杂度不会超过 O(N log N)。
    • DFS 预处理访问每个节点和每条边一次，所以是 O(N) 的。
    • 每个查询只需要进行几次计算和一次数组访问，是 O(1) 的。总查询时间是 O(Q)。
    • 所以总时间复杂度是 O(N log N + Q)。
  • 空间复杂度: O(N) 的说。
    • 邻接表 children 存储了 N-1 条边，空间是 O(N)。
    • dfs_order, time_in, time_out, next_index 这些辅助数组的大小都和 N 成正比，所以是 O(N)。
    • DFS 用的栈，在最坏情况下（一条长链）深度为 N，所以也是 O(N)。
    • 总空间复杂度就是 O(N)。

知识点与总结，快拿小本本记下来！ ​

这道题真是太棒了，让我们学到了好多东西呢，喵~

  1. DFS序 (DFS Order)：这是解决树上子树问题的超级法宝！通过一次DFS把树形结构“拍平”成一个线性序列，子树的操作就变成了序列上的区间操作，非常方便。
  2. 时间戳 (Timestamps)：time_in 和 time_out 这种时间戳技巧，可以让我们在 O(1) 的时间内判断节点的祖先关系、子树范围等信息，是树论算法中的常客哦。
  3. 预处理思想：面对大量查询，先花时间进行预处理，把能算的信息都算出来，然后快速回答查询。这是从“暴力”走向“优雅”的关键一步！
  4. 迭代DFS：当题目数据规模很大，树的深度可能很深时，使用栈实现的迭代DFS可以有效避免递归爆栈的风险，是一种非常稳健的写法。

希望这次的讲解能帮到你！只要掌握了DFS序和预处理的思想，以后遇到类似的树上查询问题，你也能像本猫娘一样，一爪子就把它解决掉！继续加油哦，未来的算法大师，喵~！(ฅ'ω'ฅ)

Released under the MIT License.

Copyright © 2024-present Moe