G. Ksyusha and Chinchilla - 题解

比赛与标签

比赛: Codeforces Round 874 (Div. 3) 标签: constructive algorithms, dfs and similar, dp, dsu, greedy, implementation, trees, *1800 难度: *1800

题目大意喵~

Ksyusha酱有一棵有 n 个节点的树和一把大剪刀，她想把这棵树剪成好多好多的小“树枝”来逗她的龙猫玩呐。一个“树枝”被定义为一个拥有3个节点的树。

我们的任务是，通过剪断树上的一些边，使得整棵树被完美地分割成若干个互不相交的“树枝”。也就是说，分割完成后，每个节点都必须恰好属于一个“树枝”。

如果能做到，我们就需要告诉Ksyusha酱要剪掉几条边，以及具体是哪些边（按照边的输入顺序，从1开始编号）。如果无论如何都做不到，就要告诉她这是不可能的，输出 -1 啦。

简单来说，就是要把一个 n 个点的大树，切成 n/3 个 3个点的小树块。

解题思路呐

喵哈哈，一看到在树上进行分割，本猫娘的DNA就动了！这通常都和 深度优先搜索 (DFS) 或者 树形DP 有关哦！我们可以从树的叶子节点开始，一步步向根节点思考。

关键的第一步：检查节点总数

首先，一个最最基本的观察是：既然每个小树枝都有3个节点，那么为了能完美分割，整棵树的总节点数 n 必须是3的倍数才行呀！如果 n 除以3有余数，那肯定会有一些节点落单，不可能完成任务。所以，如果 n % 3 != 0，我们就可以直接自信地告诉Ksyusha酱：“不行喵！”，然后输出 -1 啦。

核心思想：自底向上的贪心策略

通过了节点数检查后，我们就可以开始设计算法了。我们可以采用一种自底向上（也就是从叶子到根）的贪心策略。具体来说，我们可以进行一次深度优先搜索（DFS），在“回溯”的阶段（也就是后序遍历）处理信息。

我们来定义一下 sz[u] 的含义：它表示以 u 为根的子树中，经过内部切割后，最终汇集到 u 这里的、尚未形成完整“树枝”的节点数量。

现在，让我们从一个任意的根节点（比如1号点）开始DFS吧！

1. DFS深入: 当我们从节点 u 访问它的一个孩子 v 时，我们先不对 u 做任何事，而是继续深入，直到访问到叶子节点。

2. 处理叶子: 对于一个叶子节点 v，它的子树里只有它自己，所以 sz[v] 初始化为 1。

3. 回溯与合并: 当我们从对 v 的DFS调用中返回到父节点 u 时，我们就知道了 sz[v] 的值。这时，关键的贪心决策就来了喵！

   • 情况一：sz[v] == 3 这说明以 v 为根的这个小组件（它包含了 v 和它下面一些没被切掉的后代）大小正好是3！太棒了，它们可以自己组成一个完美的“树枝”！我们就可以果断地剪断连接 u 和 v 的这条边。这条边被剪掉后，v 的这个组件就独立了，不会再影响到 u 和树的其他部分。所以我们把这条边的编号记录下来，并且 v 组件的节点数不会计入 u 的组件中。
   • 情况二：sz[v] != 3 这说明 v 所在的组件还不能独立成为一个“树枝”。它必须和父节点 u 连接在一起，才有希望在未来和别的节点凑成3个。所以，我们不能剪断 (u, v) 这条边，而是要把 v 组件的节点数累加到 u 的组件里，即 sz[u] += sz[v]。

4. 根节点的处理: 当整个DFS过程结束时，我们回到了最初的根节点（比如1号点）。此时，sz[1] 就代表了根节点所在的那个组件的大小。根据我们的逻辑，如果整棵树能被完美分割，那么根节点所在的最后一个组件的大小也必须是3。如果 sz[1] 不等于3，那就说明最后剩下了一堆凑不齐的节点，任务失败，输出 -1。

这个贪心策略为什么是正确的呢？因为每当我们发现一个大小为3的组件时，立即将其切掉是最优的选择。这使得问题规模减小，并且不会影响剩余部分形成“树枝”的可能性。把一个能自给自足的小团体先“嫁出去”，剩下的节点才能更自由地配对呀，喵~

最终，我们需要剪断的边数正好是 n/3 - 1 条。因为一棵树有 n 个节点，要把它变成 k 个连通块，需要剪断 k-1 条边。在这里 k = n/3。

代码实现呀

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

using namespace std;

int main() {
    // 加速输入输出，让程序跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        // 使用邻接表来存树，同时存下边的编号
        vector<vector<pair<int, int>>> graph(n + 1);
        for (int i = 1; i <= n - 1; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back({v, i});
            graph[v].push_back({u, i});
        }

        // 最重要的初步判断！如果节点数不是3的倍数，直接说拜拜~
        if (n % 3 != 0) {
            cout << "-1\n";
            continue;
        }

        // sz[u] 表示以u为根的组件在内部切割后，剩余的大小
        vector<int> sz(n + 1, 1);
        vector<int> parent(n + 1, 0); // 记录DFS树中每个节点的父节点
        vector<int> next_idx(n + 1, 0); // 辅助迭代式DFS，记录访问到哪个邻居了
        vector<int> cuts; // 存放要剪断的边的编号
        
        stack<int> st; // 用栈来模拟递归，实现迭代式DFS
        st.push(1); // 从1号节点开始
        parent[1] = 0; // 根节点的父亲是0

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

            // 这个if分支是DFS的“向下”过程（前序遍历部分）
            if (next_idx[u] < graph[u].size()) {
                auto [v, idx] = graph[u][next_idx[u]];
                next_idx[u]++; // 处理下一个邻居
                
                // 如果是父节点，就跳过，防止在树上反复横跳
                if (v == parent[u]) {
                    continue;
                }
                
                parent[v] = u; // 记录父子关系
                st.push(v); // 将子节点压入栈，继续深入
            } 
            // 这个else分支是DFS的“回溯”过程（后序遍历部分）
            // 当一个节点的所有子节点都处理完毕后，就会进入这里
            else {
                st.pop(); // 处理完毕，弹出当前节点
                
                // 遍历u的所有邻居，找到它的孩子们
                for (auto [v, idx] : graph[u]) {
                    if (v == parent[u]) continue; // 再次跳过父节点
                    
                    // 这是核心贪心逻辑！
                    if (sz[v] == 3) {
                        // 如果子节点v的组件大小正好是3，太棒了！剪断这条边！
                        cuts.push_back(idx);
                    } else {
                        // 否则，v的组件必须和u合并
                        sz[u] += sz[v];
                    }
                }
            }
        }

        // 最后检查根节点所在的组件大小是否也为3
        if (sz[1] != 3) {
            cout << "-1\n";
        } else {
            // 成功啦！输出答案
            cout << cuts.size() << '\n';
            if (cuts.size() > 0) {
                // 为了格式美观，可以排个序再输出
                sort(cuts.begin(), cuts.end());
                for (int i = 0; i < cuts.size(); i++) {
                    if (i > 0) cout << ' ';
                    cout << cuts[i];
                }
                cout << '\n';
            } else {
                // 如果n=3，不需要切割，cuts为空，输出一个空行
                cout << '\n';
            }
        }
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(N) 的说。我们使用DFS遍历了整棵树。每个节点和每条边都只会被访问常数次。虽然最后对 cuts 数组进行了排序，但 cuts 的大小 k 最多是 (N/3) - 1，所以排序的复杂度是 O(k log k)，也就是 O(N log N)。不过由于 N 和 sum(N) 的限制，整体还是非常快的，可以认为是 O(N) 级别。
• 空间复杂度: O(N) 的说。我们需要一个邻接表 graph 来存储树，大小和边数（N-1）成正比。还需要 sz, parent 等辅助数组，以及DFS用的栈，它们的大小都和节点数 N 成正比。

知识点与总结喵

这道题真是一道非常好的练习题，它融合了几个重要的知识点呢！

1. 树的遍历 (DFS): 解决树上问题的基本功！无论是递归还是用栈模拟的迭代写法，都要熟练掌握呐。
2. 贪心算法 (Greedy Approach): 本题的核心就是那个自底向上的贪心策略。在每个子树中，一旦有机会形成一个符合条件的3节点“树枝”，就果断地切割。这种“局部最优”的选择最终导向了“全局最优”，是贪心思想的完美体现。
3. 树形动态规划 (Tree DP) 的思想: 虽然我们没有明确定义 dp 数组，但 sz[u] 的计算过程其实就是树形DP的雏形。它通过子问题（子树）的解来构建当前问题的解。
4. 问题分解: 先处理最简单的必要条件（n % 3 == 0），可以排除很多无效情况，简化后续的逻辑。这是解题的一个好习惯哦！

希望这篇题解能帮助你更好地理解这个问题！只要跟着猫娘的思路一步步来，再复杂的树问题也能被轻松解决的！加油，你一定可以的，喵~！