D. Vertical Paths - 题解

比赛与标签

比赛: Codeforces Round 787 (Div. 3) 标签: graphs, implementation, trees 难度: *1300

题目大意喵~

喵哈~！各位算法大师们好呀！今天我们来解决一个关于树的路径划分问题，很有趣的哦~

题目会给我们一棵有根树，它由一个父节点数组 p 来表示。p[i] 代表节点 i 的父节点是谁。特别地，如果 p[i] = i，那么 i 就是这棵树的根节点啦。

我们的任务是，把这棵树里的所有节点，划分成若干条路径。这些路径需要满足以下条件：

每个节点都必须属于 且仅属于 一条路径。
每条路径都必须是 从上到下 的，也就是说，路径中的下一个节点必须是当前节点的儿子。
我们需要找到一种划分方案，使得路径的总数量最少。

最后，我们要输出最少的路径数量，以及每一条路径的具体内容。

寻找路径的猫爪印🐾

要让路径数量最少，我们应该怎么做呢喵？让我们一起动动脑筋！

首先，我们来观察一下路径的特点。题目要求路径必须是从上到下（从父到子）的。那么，一条路径的终点会是什么样的节点呢？它肯定是一个没有子节点的节点，否则路径就可以继续向下延伸了嘛。在树里，这种没有子节点的节点，我们亲切地称它为 叶子节点 的说！

既然每条路径都必须有一个终点，而且这个终点很自然地就是一个叶子节点，那么我们可以得出一个超级重要的结论：每一个叶子节点，都必须作为某一条路径的终点。因为如果一个叶子节点不是任何路径的终点，那它又该如何被覆盖呢？它没有孩子，无法成为路径的中间节点；如果它是起点，那这条路径只有一个节点，它自己就是终点。所以，每个叶子都必须是某条路径的终点。

每条路径只有一个终点，而我们有 k 个叶子节点都需要被当做终点。所以，我们至少需要 k 条路径才能覆盖所有的叶子节点，对不对呀？

哇！这真是一个惊人的发现！最小路径数就等于叶子节点的数量！

找到了最小路径数，我们该如何具体地构造出这些路径呢？

策略其实非常直接喵！既然我们确定了要以每个叶子节点作为终点来构建路径，那我们就这么做：

首先，通过父节点数组 p，我们可以轻松地构建出每个节点的子节点列表。这样就能快速找到谁是叶子节点（也就是子节点列表为空的节点）。
我们从任意一个叶子节点开始，比如说 leaf_A。
我们从 leaf_A 出发，沿着父节点指针 向上回溯，一步步走向根节点。这条回溯的轨迹 ... -> parent_of_parent -> parent -> leaf_A 就是一条合法的从上到下的路径，只是我们是反着找到它的。
我们将这条路径上的所有节点都标记为“已访问”，表示它们已经被分配了归宿。
接着，我们再找下一个 还没有被访问过 的叶子节点，重复上面的过程，构建出第二条路径。
我们不断重复这个过程，直到所有的叶子节点都被作为起点（从下往上看是起点）处理过。

这个方法为什么是正确的呢？因为我们从所有的叶子节点出发，向上延伸路径，直到碰到一个已经被其他路径“预定”的节点。这样可以保证，树上的任何一个节点 u，都会被它子树中某个叶子节点延伸上来的路径所覆盖，而且由于有“已访问”标记，它只会被覆盖一次。完美地满足了题目的所有要求呐！

所以，算法步骤就是：

建树（子节点列表）。
找到所有叶子节点。
输出叶子节点的数量。
对每个叶子节点，向上回溯生成路径，直到遇到已访问节点或根，然后输出这条路径。

代码魔法时间✨

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    int n;
    std::cin >> n;
    // p[i] 存的是节点 i 的父亲喵~ 我们用从1开始的下标哦
    std::vector<int> p(n + 1);
    // children[i] 用来存节点 i 的所有孩子，方便我们找叶子节点
    std::vector<std::vector<int>> children(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> p[i];
        // 如果 p[i] != i，说明 i 不是根节点，它有父亲
        // 我们就把 i 添加到它父亲 p[i] 的孩子列表里
        if (p[i] != i) {
            children[p[i]].push_back(i);
        }
    }

    // 一个节点如果没有孩子，它就是可爱的叶子节点啦！
    std::vector<int> leaves;
    for (int i = 1; i <= n; ++i) {
        if (children[i].empty()) {
            leaves.push_back(i);
        }
    }

    // 最少路径数就是叶子节点的数量，直接输出！
    std::cout << leaves.size() << "\n";

    // visited数组用来标记一个节点是否已经被分配到某条路径里了
    std::vector<bool> visited(n + 1, false);

    // 从每个叶子开始，向上回溯构造路径
    for (int leaf : leaves) {
        std::vector<int> current_path;
        int curr = leaf;
        
        // 向上回溯，直到碰到根或者已经被访问过的节点
        while (true) {
            // 如果当前节点已经被其他路径占领了，就停下来
            if (visited[curr]) {
                break;
            }
            // 把当前节点加入路径，并标记为已访问
            current_path.push_back(curr);
            visited[curr] = true;
            
            // 如果到达了根节点（它的父亲是它自己），路径就到头了
            if (p[curr] == curr) {
                break;
            }
            
            // 继续向上走，去找父亲
            curr = p[curr];
        }
        
        // 因为我们是从叶子->根这样从下往上找的，所以要反转一下
        // 才能得到题目要求的从上到下的路径顺序哦
        std::reverse(current_path.begin(), current_path.end());
        
        // 按格式输出这条路径
        std::cout << current_path.size() << "\n";
        for (size_t i = 0; i < current_path.size(); ++i) {
            std::cout << current_path[i] << (i == current_path.size() - 1 ? "" : " ");
        }
        std::cout << "\n";
    }
}

int main() {
    // 加上这个可以让输入输出快一点，是个好习惯喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

复杂度分析

时间复杂度: O(N) 的说。其中 N 是所有测试用例中节点数的总和。对于每个测试用例，我们遍历所有节点来建树（O(n)），遍历所有节点来找叶子（O(n)），然后从每个叶子出发向上回溯。因为每个节点只会被访问并标记一次，所以所有回溯操作的总和也是 O(n)。因此，总体是线性的！
空间复杂度: O(N) 的说。我们主要使用了 p 数组、children 邻接表和 visited 数组来存储信息，它们的大小都和节点数 n 成正比。

猫娘的小课堂🎓

这道题虽然是图论题，但思路非常巧妙，让我们来总结一下学到了什么吧！

核心洞察: 这道题最关键的就是发现 “最小路径数 = 叶子节点数” 这个性质。在处理树或图的路径覆盖问题时，分析路径端点的性质常常是找到突破口的关键！抓住这个性质，问题就迎刃而解了喵~
图的表示转换: 题目给了父节点数组，这是一种表示树的方式。但为了方便找到叶子节点（即出度为0的节点），我们把它转换成了子节点邻接表。根据问题的需要，灵活选择或转换图的表示方法，是每个算法高手的基本功哦。
逆向思维: 我们没有尝试从根节点开始向下搜索如何划分路径（这会非常复杂），而是采用了从叶子节点 向上回溯 的策略。这种“反过来想”的思路在很多算法问题中都超级有用，能化繁为简，值得我们学习和模仿呐！
实现细节: 在实现时，使用 visited 数组来确保每个节点只属于一条路径是至关重要的。还有，别忘了我们是从下往上构建的路径，所以在输出前要 reverse 一下，变成从上到下的顺序。

好啦，这次的题解就到这里啦！希望对大家有帮助喵~ 继续加油，下一个AC就是你的！🐾

D. Vertical Paths - 题解 ​

比赛与标签 ​

题目大意喵~ ​

寻找路径的猫爪印🐾 ​

代码魔法时间✨ ​

复杂度分析 ​

猫娘的小课堂🎓 ​