CovertheTree - 题解

标签与难度

标签: 树论, 深度优先搜索, 图论, 树的性质, 路径覆盖, 构造难度: 1600

题目大意喵~

你好呀，未来的算法大师！今天我们遇到了一道关于树的可爱问题，喵~ 题目是这样的：

给你一棵无根树，你需要选择最少数量的链（也就是路径），使得树上的每一条边都至少被一条链覆盖。

任务是输出两个东西：

你找到的最少链的数量。
这些链的具体方案，也就是每条链的两个端点是哪个节点。

如果有很多种合法的方案，随便输出一种就可以啦，呐！

解题思路分析

这道题是要我们用最少的路径覆盖整棵树，听起来是不是有点小挑战？别怕别怕，跟着本喵的思路，一步一步就能解开谜题的！

关键的突破口：叶子节点！

首先，我们来想想树上什么样的边最“特殊”呢？当然是连接着叶子节点的边啦！一个叶子节点，就是度为 1 的节点，只跟一个邻居相连。

想象一下，连接叶子节点 L 的那条唯一的边 (L, P)，要怎么才能被覆盖呢？答案只有一个：必须有一条我们选择的链，其端点就是这个叶子节点 L。这条链要么从 L 开始，要么在 L 结束。

所以，我们得出一个超——重要的结论：树上所有的叶子节点，都必须是某条链的端点。

最小链数是多少呢？

好啦，既然每个叶子都必须是端点，而一条链有两个端点，那它最多能“满足”两个叶子节点的需求。

假设这棵树一共有 $k$ 个叶子节点。

如果我们把叶子们两两配对，比如叶子 $L_1$ 和 $L_2$ 配成一条链，叶子 $L_3$ 和 $L_4$ 配成一条链…… 这样每条链消耗两个叶子，我们总共需要 $k/2$ 条链。
但如果 $k$ 是奇数怎么办？比如有 5 个叶子。我们可以先配对前 4 个，得到 2 条链。还剩下一个孤零零的叶子 $L_5$ 。它也必须是一个端点呀！没办法，我们只好为它单独创建一条链，这条链的另一个端点可以是树上任意其他节点。这样就又多了一条链。

综合一下，我们需要的链数似乎是：

如果 $k$ 是偶数，需要 $k/2$ 条。
如果 $k$ 是奇数，需要 $(k-1)/2 + 1 = (k+1)/2$ 条。

这两种情况可以统一成一个漂亮的公式： $\lceil k/2 \rceil$ ，也就是 $k$ 除以 2 向上取整。这也就是 (k+1)/2 在整数除法下的结果啦。

这个数量是下限，但它是否也足够覆盖所有边呢？答案是肯定的！只要我们聪明地配对叶子，就能保证所有边都被覆盖。

如何聪明地配对？

随机配对可不行哦，可能会漏掉树中心的某些边。我们需要一个系统性的方法。一个非常可靠的策略是利用**深度优先搜索（DFS）**来给叶子们排个序。

找一个根：随便找一个非叶子节点（度 > 1）作为根节点 root。如果整棵树是一条链（所有节点度数 $\le 2$ ），那随便哪个节点当根都行。
DFS 遍历：从 root 开始进行 DFS。当我们遍历到一个节点 u，并且发现它是一个叶子节点时，就把它加到一个列表 leaves 里。
有序的叶子：当 DFS 结束后，leaves 列表里的叶子们就是按照 DFS 访问顺序排列的。这个顺序很有用，因为它大致反映了叶子在树上的“位置”。比如，同一个子树下的叶子们会在列表里挨在一起。

最终的配对策略！

现在我们有了一个有序的叶子列表 leaves，大小为 $k$ 。配对就变得很简单啦！

一个非常经典且有效的配对方法是：将列表的前半部分与后半部分一一对应配对。

设 half = k / 2。
我们把 leaves[0] 和 leaves[half] 配对。
把 leaves[1] 和 leaves[half + 1] 配对。
...
一直到 leaves[half - 1] 和 leaves[k - 1]（如果k是偶数）或者 leaves[k-2]（如果k是奇数）配对。

这种“远距离”配对几乎总能保证路径会穿过树的中心区域，从而覆盖所有边。

那如果 $k$ 是奇数呢？按上面的方法，leaves[half] 到 leaves[k-2] 都被配对好了，但最后一个叶子 leaves[k-1] 剩下了。怎么办？很简单，把它和任意一个其他节点配对就行。为了方便，我们可以把它和我们选的 root 节点配对，或者和列表里的第一个叶子 leaves[0] 配对。这两种方法都能保证覆盖所有边。

总结一下我们的算法步骤：

读入树的边，计算每个节点的度数。
找出所有的叶子节点（度为1的节点）。
如果叶子数量 $k=0$ (只有1个节点) 或 $k=2$ (只有2个节点)，特殊处理。
选择一个度 > 1 的节点作为 root。
从 root 开始 DFS，按顺序收集所有叶子节点到 leaves 列表中。
计算所需链数 $m = (k+1)/2$ 并输出。
进行配对：
- half = k / 2。
- 对于 i 从 0 到 half - 1，输出一对 (leaves[i], leaves[i + half])。
- 如果 $k$ 是奇数，会剩下 leaves[k-1]。我们把它和 leaves[0] 配对并输出。

这样，我们就完美地解决了这个问题，喵~

代码实现

这是本喵根据上面的思路，精心重构的一份代码，注释超详细的，希望能帮助你理解哦！

cpp

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

// 用于存储图的邻接表
std::vector<int> adj[200005];
// 存储每个节点的度数
int degree[200005];
// 存储按DFS顺序找到的叶子节点
std::vector<int> leaves;
// 访问标记数组，防止DFS时重复访问
bool visited[200005];

// DFS函数，用于按顺序查找叶子节点
void find_leaves_dfs(int u, int p) {
    visited[u] = true;
    
    // 如果当前节点是叶子节点（度为1），就将它加入列表
    // 对于n>2的树，根节点不会是叶子，所以这个判断是安全的
    if (degree[u] == 1) {
        leaves.push_back(u);
    }

    // 遍历所有邻居
    for (int v : adj[u]) {
        // 如果邻居不是父节点且未被访问过
        if (v != p) {
            find_leaves_dfs(v, u);
        }
    }
}

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 处理特殊情况
    if (n == 1) {
        std::cout << 0 << std::endl;
        return 0;
    }

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }

    if (n == 2) {
        std::cout << 1 << std::endl;
        std::cout << 1 << " " << 2 << std::endl;
        return 0;
    }

    // 找到一个非叶子节点作为DFS的根
    int root = -1;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] > 1) {
            root = i;
            break;
        }
    }
    
    // 从根节点开始DFS，找到所有叶子
    find_leaves_dfs(root, -1);

    int k = leaves.size();
    // 计算并输出最小链数
    int num_paths = (k + 1) / 2;
    std::cout << num_paths << std::endl;

    int half = k / 2;
    // 将叶子列表的前半部分与后半部分配对
    for (int i = 0; i < half; ++i) {
        std::cout << leaves[i] << " " << leaves[i + half] << std::endl;
    }

    // 如果叶子数量是奇数，最后一个叶子会剩下
    // 我们将它与第一个叶子配对
    if (k % 2 == 1) {
        std::cout << leaves[k - 1] << " " << leaves[0] << std::endl;
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N)$
- 读入 $N-1$ 条边并构建邻接表、计算度数，需要 $O(N)$ 的时间。
- 寻找根节点最多遍历 $N$ 个节点，为 $O(N)$ 。
- 深度优先搜索 find_leaves_dfs 会访问每个节点和每条边一次，所以是 $O(N)$ 。
- 最后的配对和输出操作，时间与叶子数量 $k$ 成正比，而 $k \le N$ ，所以是 $O(k)$ 或 $O(N)$ 。
- 总的时间复杂度是线性的，也就是 $O(N)$ ，非常高效！
空间复杂度: $O(N)$
- 邻接表 adj 存储了 $2(N-1)$ 条边，空间为 $O(N)$ 。
- degree, visited 数组大小都是 $N$ ，空间为 $O(N)$ 。
- leaves 向量最多存储 $N-1$ 个叶子，空间为 $O(N)$ 。
- 所以总的空间复杂度也是 $O(N)$ 。

知识点总结

这道题虽然看似简单，但背后蕴含着一些深刻的树论思想，值得我们好好回味，喵~

叶子节点的重要性：在很多树形问题中，叶子节点都是关键的切入点。它们的性质（度为1）常常能大大简化问题。
路径覆盖与度数：一个节点如果是奇数度，那么在任何一个能覆盖所有 incident 边的路径集合中，必须有奇数条路径以它为端点。叶子节点度为1，所以必须是端点。这个奇偶性分析是图论中的一个常用技巧。
DFS的应用：DFS 不仅仅是用来遍历图，它还能根据遍历顺序，为节点（尤其是叶子节点）提供一个有意义的、结构化的排序，这在构造解法时非常有用。
构造性算法：这类问题不仅要你求一个最优值，还要你给出具体方案。关键在于找到一个具有普适性的、正确的构造策略。我们这里的“DFS排序 + 前后半段配对”就是一种强大的构造策略。

希望这篇题解能帮到你！继续加油，探索更多算法的奥秘吧，喵~！

CovertheTree - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键的突破口：叶子节点！ ​

最小链数是多少呢？ ​

如何聪明地配对？ ​

最终的配对策略！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​