题目描述

存在 N 种病毒，编号从 0 到 N-1。病毒之间存在变异关系，形成一个有向结构。每一种病毒都是由唯一的另一种病毒突变而来（除了最初的“源头”病毒），并且不存在循环变异（例如 A->B->C->A）。这意味着这种变异关系构成了一个以某个病毒为根的有向树结构（或者严格来说，是一个有向无环图 DAG，但题目保证了源头唯一且无环，实际就是树）。

我们需要找出从“源头”病毒开始的最长的一条变异链（即树中从根出发的最长路径）。
长度定义为链上包含的病毒种类数（即路径上的节点数）。
如果存在多条最长链，需要输出字典序最小的那一条链。序列 $\{a_1,…,a_n\}$ 比序列 $\{b_1,…,b_n\}$ “小”，是指存在 $k$ 使得 $a_i = b_i$ 对所有 $i < k$ 成立，且 $a_k < b_k$。

输入格式描述了每个病毒 i 可以变异成哪些病毒（它的直接子节点）。

输出格式要求先输出最长链的长度，然后在下一行输出该链上的病毒编号序列，用空格隔开。

样例

输入:
10
3 6 4 8
0
0
0
2 5 9
0
1 7
1 2
0
2 3 1
输出:
4
0 4 9 1

说明：源头是 0。有多条路径，例如 0->6->7->2，长度为 4。0->4->9->1，长度为 4。0->8，长度为 2。0->4->5，长度为 3。最长的链长度是 4。在长度为 4 的链中，(0, 4, 9, 1) 比 (0, 6, 7, 2) 字典序小（因为在第二个元素处 4 < 6）。

算法 (树形 DP / DFS + 贪心)

$O(N + E)$ 其中 E 是变异关系的总数

思路分析

1. 建模:
   病毒之间的变异关系可以看作一个有向图。节点代表病毒，有向边 u -> v 表示病毒 u 可以变异成病毒 v。根据题目描述（每种病毒由唯一病毒突变而来，无环，源头唯一），这个图实际上是一个以源头病毒为根的有向树。我们要找的就是树中从根节点出发的最长路径，并且在长度相同时选择字典序最小的路径。

2. 寻找源头:
   源头病毒是唯一没有其他病毒可以变异成它的病毒。在图论中，这意味着源头节点的入度 (in-degree) 为 0。我们可以通过计算每个节点的入度来找到源头。在读取输入构建图的同时，维护一个 deg 数组记录每个节点的入度。然后找到 deg[i] == 0 的那个节点 i，它就是源头 src。

3. 寻找最长路径 (长度):
   这是一个经典的树上动态规划问题。我们可以定义 dp[u] 为从节点 u 出发（包含 u 自身）的最长路径的长度。
   状态转移方程为：
   $$dp[u] = 1 + \max_{v \in children(u)} \{ dp[v] \}$$
   如果 u 是叶子节点（没有子节点），则 $dp[u] = 1$。
   我们可以使用深度优先搜索 (DFS) 结合记忆化来实现这个 DP。函数 dfs(u) 计算并返回 dp[u]。为了避免重复计算，使用一个数组（如 len_dp）来存储已计算出的 dp 值，初始化为 -1。

4. 寻找字典序最小的最长路径 (路径本身):
   仅仅计算长度是不够的，我们还需要记录路径。同时，当存在多条最长路径时，要选择字典序最小的。
   字典序的比较是从路径的第一个节点开始的。为了得到整体字典序最小的路径，当我们在节点 u 决定下一步走向哪个子节点 v 时，如果多个子节点都能导出同样的最长路径长度 (1 + dp[v] == max_length_from_u)，我们应该选择那个编号最小的子节点 v。因为选择编号小的子节点会使得路径在尽可能早的位置拥有更小的编号，从而使得整个路径的字典序更小。

5. 结合长度和字典序的 DP/DFS:
   我们可以修改 DFS 函数，让它不仅返回最长路径的长度，还返回导致这条路径的下一个节点的编号。

   • 定义 len_dp[u] 存储从 u 出发的最长路径长度。
   • 定义 next_dp[u] 存储从 u 出发的最长路径（且是字典序最小的那条）的下一个节点的编号。如果 u 是最长路径的终点，next_dp[u] 可以设为 -1。
   • DFS 函数 dfs(u) 返回一个 pair<int, int>，即 {len_dp[u], next_dp[u]}。
   • 在 dfs(u) 内部：
     • 检查备忘录 len_dp[u]。如果已计算，直接返回。
     • 初始化 max_l = 1 (至少包含节点 u 本身)，best_n = -1 (当前没有找到下一跳)。
     • 获取 u 的所有子节点 children = g[u]。
     • 关键点：将子节点按编号升序排序 std::sort(children.begin(), children.end())。
     • 遍历排序后的子节点 v:
       • 递归调用 child_res = dfs(v) 获取子节点 v 的结果 {child_len, _}。
       • 计算经过 v 的路径长度 cur_len = 1 + child_len。
       • 比较 cur_len 和 max_l:
         • 如果 cur_len > max_l：发现了更长的路径。更新 max_l = cur_len，并将 best_n 更新为当前的子节点 v。
         • 如果 cur_len == max_l：长度相同。因为我们是按子节点编号升序遍历的，所以当前的 best_n (如果已设置) 一定是之前遇到的编号更小的子节点。因此，不需要更新 best_n，保持选择编号最小的那个子节点。
     • 存储结果：len_dp[u] = max_l, next_dp[u] = best_n。
     • 返回 {max_l, best_n}。

6. 获取最终结果:

   • 调用 dfs(src) 得到源头开始的最长链长度 total_length 和链上的第一个后继节点 first_next。
   • 输出 total_length。
   • 从 src 开始，利用 next_dp 数组回溯路径：当前节点 curr = src，不断将 curr 加入路径列表，然后令 curr = next_dp[curr]，直到 curr 变为 -1。
   • 输出构建好的路径列表。

时间复杂度

• 构建图和计算入度：遍历所有变异关系，设总关系数为 E (最多 $N \times k_{avg}$，但总和不超过 $N \times \text{最大k}$ 或某个限制，通常接近 $O(N)$ 或 $O(N+M)$ 级别，如果 M 是边数)。复杂度为 $O(N + E)$。
• 寻找源头：$O(N)$。
• DFS + 记忆化：每个节点和每条边最多访问一次。对子节点排序需要时间，如果一个节点有 $k$ 个子节点，排序需要 $O(k \log k)$。总的排序时间是 $\sum_{u} \text{deg}_{out}(u) \log \text{deg}_{out}(u)$。最坏情况下，如果是一个星形图，可能是 $O(N \log N)$。总 DFS 复杂度大致为 $O(N + E + \sum \dots)$，通常认为是 $O(N+E)$ 或 $O(N \log N)$ (如果排序是瓶颈)。
• 路径回溯：$O(N)$。
• 总体复杂度主要由建图和 DFS 决定，为 $O(N + E + \text{SortTime})$，近似为 $O(N + E)$ 或 $O(N \log N)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;

// 定义类型别名，方便书写 (虽然本题中 i64 等未使用)
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

int main() {
    // 加速 IO
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n; // 病毒种类总数
    std::cin >> n;

    // g[i] 存储病毒 i 可以变异成的病毒列表 (邻接表表示有向图)
    std::vector<std::vector<int>> g(n);
    // deg[i] 存储病毒 i 的入度 (有多少种病毒可以变异成 i)
    std::vector<int> deg(n, 0);

    // 读取输入，构建图并计算入度
    for (int i = 0; i < n; ++i) { // 处理编号为 i 的病毒
        int k; // 病毒 i 可以变异成的种类数
        std::cin >> k;
        for (int j = 0; j < k; ++j) {
            int target; // 变异目标的编号
            std::cin >> target;
            // 添加有向边 i -> target
            g[i].push_back(target);
            // 增加目标病毒 target 的入度
            // 加入简单的边界检查，虽然题目数据可能保证 target 有效
            if (target >= 0 && target < n) {
                 deg[target]++;
            }
        }
    }

    // 寻找源头节点 (入度为 0 的节点)
    int src = -1; // 源头节点编号
    for (int i = 0; i < n; ++i) {
        if (deg[i] == 0) {
            src = i;
            break; // 题目保证源头唯一，找到即可退出
        }
    }

    // DP 数组进行记忆化搜索
    // len_dp[u]: 从节点 u 出发的最长链长度
    std::vector<int> len_dp(n, -1);
    // next_dp[u]: 从节点 u 出发的最长链 (且字典序最小) 的下一个节点编号
    std::vector<int> next_dp(n, -1);

    // 定义 DFS 函数返回的结果类型: {长度, 下一个节点}
    using Res = std::pair<int, int>;

    // 定义 DFS 函数 (使用 lambda 表达式和 std::function)
    std::function<Res(int)> dfs =
        [&](int u) -> Res { // u 是当前节点编号

        // 检查是否已经计算过 u 的结果 (记忆化)
        if (len_dp[u] != -1) {
            return {len_dp[u], next_dp[u]};
        }

        // 初始化从 u 出发的最长链信息
        int max_l = 1; // 最小长度为 1 (包含 u 自身)
        int best_n = -1; // 初始没有下一跳

        // 获取 u 的所有子节点 (变异目标)
        std::vector<int> children = g[u];
        // 按子节点编号升序排序，以处理字典序最小的要求
        std::sort(children.begin(), children.end());

        // 遍历排序后的子节点 v
        for (int v : children) {
            // 递归计算子节点 v 的结果
            Res child_res = dfs(v);
            // 计算经过子节点 v 的链长度
            int cur_len = 1 + child_res.first;

            // 如果找到更长的链
            if (cur_len > max_l) {
                max_l = cur_len; // 更新最大长度
                best_n = v;      // 更新下一跳节点
            }
            // 如果长度相同，由于 children 已排序，
            // 当前 best_n 对应的节点编号一定小于等于 v，
            // 不需要更新 best_n，保持字典序最小。
        }

        // 存储计算结果 (记忆化)
        len_dp[u] = max_l;
        next_dp[u] = best_n;

        // 返回结果
        return {len_dp[u], next_dp[u]};
    };

    // 从源头节点开始 DFS
    Res src_res = dfs(src);

    // 输出最长链的长度
    std::cout << src_res.first << "\n";

    // 回溯构造最长链 (且字典序最小)
    std::vector<int> path;
    int curr = src; // 从源头开始
    while (curr != -1) { // 只要还有下一跳
        path.push_back(curr); // 将当前节点加入路径
        curr = next_dp[curr]; // 移动到下一跳节点
    }

    // 输出路径
    for (size_t i = 0; i < path.size(); ++i) {
        std::cout << path[i] << (i == path.size() - 1 ? "" : " "); // 输出节点编号，用空格分隔，末尾无空格
    }
    std::cout << "\n";

    return 0; // 程序正常结束
}