题目描述

给定一棵有 $n$ 个结点的多叉树，结点编号从 1 到 $n$。输入提供了每个结点（除了根结点）的父结点编号，根结点的父结点编号为 0。

定义：
树中结点的度是指其拥有的子树的个数（即子结点的数量）。
树的度是指树中所有结点度的最大值。
* 一棵k 阶满树是指树中所有非叶结点的度都等于 $k$ 的树。注意，这里的 $k$ 就是这棵树的度。叶结点没有子结点，度为 0，不受此限制。

任务：
1. 计算给定树的度。
2. 判断该树是否为其自身度数 $k$ 的 $k$ 阶满树。
3. 输出该树的前序遍历序列。

要求：
输出第一行：树的度，后面跟一个空格，然后是 yes（如果是 $k$ 阶满树）或 no（如果不是）。
输出第二行：树的前序遍历序列，数字间用空格分隔，行首尾无多余空格。
* 前序遍历时，兄弟结点（同一父结点的子结点）需要按照它们的编号升序访问。

样例 1

输入:

7
6
5
5
6
6
0
5

解释：结点 6 是根。结点 6 有子结点 1, 4, 5。结点 5 有子结点 2, 3, 7。
度的计算：
deg(1)=0, deg(2)=0, deg(3)=0, deg(4)=0, deg(7)=0 (叶结点)
deg(5)=3
deg(6)=3
树的度 = max(0, 3, 3) = 3。
判断是否 3 阶满树：非叶结点是 5 和 6。它们的度都是 3。所以是 3 阶满树。
前序遍历 (根左右，兄弟按编号升序):
6 -> 1 -> 4 -> 5 -> 2 -> 3 -> 7

输出:

3 yes
6 1 4 5 2 3 7

样例 2

输入:

7
6
5
5
6
6
0
4

解释：结点 6 是根。结点 6 有子结点 1, 4, 5。结点 5 有子结点 2, 3。结点 4 有子结点 7。
度的计算：
deg(1)=0, deg(2)=0, deg(3)=0, deg(7)=0 (叶结点)
deg(4)=1
deg(5)=2
deg(6)=3
树的度 = max(0, 1, 2, 3) = 3。
判断是否 3 阶满树：非叶结点是 4, 5, 6。它们的度分别是 1, 2, 3。因为存在非叶结点（4 和 5）的度不等于树的度 3，所以不是 3 阶满树。
前序遍历 (根左右，兄弟按编号升序):
6 -> 1 -> 4 -> 7 -> 5 -> 2 -> 3

输出:

3 no
6 1 4 7 5 2 3

算法 (树的表示与遍历)

$O(N \log N)$ 或 $O(N)$ 取决于排序

思路分析

1. 读取输入与建树:

   • 输入格式是给出每个结点的父结点。我们可以利用这个信息来构建树的邻接表表示。
   • 创建一个大小为 n+1 的邻接表 adj（使用 vector<vector<int>>），其中 adj[i] 存储结点 i 的所有子结点的编号。
   • 同时，记录父结点编号为 0 的结点，它就是树的根 root。
   • 遍历输入的父结点数组 p。对于每个结点 i（从 1 到 n），如果 p[i] 不为 0，说明 i 是 p[i] 的子结点，将 i 添加到 adj[p[i]] 的列表中。
     cpp vector<int> p(n + 1); int root; for (int i = 1; i <= n; i++) { cin >> p[i]; if (p[i] == 0) root = i; } vector<vector<int>> adj(n + 1); for (int i = 1; i <= n; i++) { if (p[i] != 0) { adj[p[i]].push_back(i); } }

2. 子结点排序:

   • 题目要求前序遍历时，兄弟结点按编号升序访问。因此，在构建完邻接表后，需要对每个结点的子结点列表 adj[i] 进行升序排序。
     cpp for (int i = 1; i <= n; i++) { sort(adj[i].begin(), adj[i].end()); }
   • 这一步的时间复杂度取决于排序算法。如果使用基于比较的排序，总时间复杂度是 $O(\sum_{i=1}^{n} |adj[i]| \log |adj[i]|)$。因为 $\sum |adj[i]| = N-1$ (树的边数)，最坏情况下（例如一条链），复杂度可能是 $O(N)$；但对于度数较高的结点，复杂度可能接近 $O(N \log N)$。

3. 计算树的度:

   • 树的度是所有结点度的最大值。结点 i 的度就是其子结点的数量，即 adj[i].size()。
   • 遍历所有结点 i 从 1 到 $n$，计算 adj[i].size()，并记录其中的最大值 max_deg。
     cpp int max_deg = 0; for (int i = 1; i <= n; i++) { max_deg = max(max_deg, (int)adj[i].size()); }
   • 这一步的时间复杂度是 $O(N)$。

4. 判断是否为 k 阶满树:

   • 根据定义，$k$ 阶满树要求所有非叶结点的度都等于树的度 $k$ (即我们计算出的 max_deg)。
   • 叶结点的度为 0。非叶结点的度大于 0。
   • 遍历所有结点 i 从 1 到 $n$：
     • 检查结点 i 是否是非叶结点。判断条件是 adj[i].empty() 为 false (即 !adj[i].empty() 或 adj[i].size() > 0)。
     • 如果 i 是非叶结点，检查它的度 adj[i].size() 是否等于 max_deg。
     • 如果发现任何一个非叶结点的度不等于 max_deg，那么该树就不是 $k$ 阶满树，设置标志 is_full = false 并可以提前结束检查。
   • 如果遍历完所有结点都没有发现违反条件的情况，则 is_full 保持 true。
     cpp bool is_full = true; for (int i = 1; i <= n; i++) { // 检查是否为非叶结点 (!adj[i].empty()) 且其度不等于 max_deg if (!adj[i].empty() && adj[i].size() != max_deg) { is_full = false; break; // 找到一个反例即可退出 } }
   • 这一步的时间复杂度是 $O(N)$。

5. 输出第一行:

   • 输出计算得到的 max_deg，然后根据 is_full 的值输出 yes 或 no。
     cpp cout << max_deg << (is_full ? " yes" : " no") << "\n";

6. 前序遍历:

   • 前序遍历的顺序是：访问根结点 -> 递归访问左子树 -> 递归访问右子树。对于多叉树，就是：访问根结点 -> 按顺序递归访问所有子树。
   • 因为我们已经对子结点列表 adj[i] 进行了排序，所以递归访问子树时自然满足兄弟按编号升序的要求。
   • 使用一个递归函数 preorder(u) 来实现：
     1. 将当前结点 u 添加到结果列表 traversal 中。
     2. 遍历 adj[u] 中的每个子结点 v。
     3. 对每个子结点 v，递归调用 preorder(v)。
   • 从根结点 root 开始调用 preorder(root)。
     cpp vector<int> traversal; // 存储遍历结果 function<void(int)> preorder = [&](int u) { traversal.push_back(u); // 访问根 for (int v : adj[u]) { // 遍历子结点 (已排序) preorder(v); // 递归访问子树 } }; preorder(root); // 从根开始遍历
   • 前序遍历会访问每个结点和每条边恰好一次，时间复杂度是 $O(N)$。

7. 输出第二行:

   • 遍历 traversal 列表，按格式输出前序遍历序列。注意数字间用空格分隔，行首尾无多余空格。
     cpp for (size_t i = 0; i < traversal.size(); i++) { if (i > 0) cout << " "; // 第一个数前不输出空格 cout << traversal[i]; } cout << "\n";

时间复杂度

• 建树: $O(N)$。
• 子结点排序: 最坏 $O(N \log N)$，平均或最好 $O(N)$。
• 计算树的度: $O(N)$。
• 判断 k 阶满树: $O(N)$。
• 前序遍历: $O(N)$。
• 输出: $O(N)$。
• 整体时间复杂度主要由子结点排序决定，为 $O(N \log N)$。如果使用桶排序等非比较排序（因为结点编号范围已知），理论上可以达到 $O(N)$。但在 C++ std::sort 下是 $O(N \log N)$。

C++ 代码

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

using namespace std; // 使用标准命名空间

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false); 
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    int n; // 结点数
    cin >> n; // 读取结点数

    // p[i] 存储结点 i 的父结点编号，使用 1-based 索引
    vector<int> p(n + 1); 
    int root; // 存储根结点的编号
    // 读取每个结点的父结点
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        if (p[i] == 0) root = i; // 父结点为 0 的是根结点
    }

    // 构建邻接表 adj，adj[i] 存储结点 i 的子结点列表
    vector<vector<int>> adj(n + 1); 
    // 遍历所有结点，构建子结点关系
    for (int i = 1; i <= n; i++) {
        if (p[i] != 0) { // 如果结点 i 不是根结点
            adj[p[i]].push_back(i); // 将 i 加入其父结点 p[i] 的子结点列表
        }
    }

    // 对每个结点的子结点列表进行升序排序，以满足遍历要求
    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end()); 
    }

    // 计算树的度 (所有结点度的最大值)
    int max_deg = 0; // 初始化最大度为 0
    for (int i = 1; i <= n; i++) {
        // 结点 i 的度是其子结点数量 adj[i].size()
        max_deg = max(max_deg, (int)adj[i].size()); // 更新最大度
    }

    // 判断该树是否为 k 阶满树 (k = max_deg)
    bool is_full = true; // 假设是 k 阶满树
    for (int i = 1; i <= n; i++) {
        // 检查非叶结点 (!adj[i].empty()) 的度是否等于 max_deg
        if (!adj[i].empty() && adj[i].size() != max_deg) { 
            is_full = false; // 如果存在度不等的非叶结点，则不是 k 阶满树
            break; // 可以提前结束检查
        }
    }

    // 输出第一行：树的度 和 判断结果
    cout << max_deg << (is_full ? " yes" : " no") << "\n";

    // 执行前序遍历
    vector<int> traversal; // 用于存储前序遍历的结果序列
    // 定义递归的前序遍历函数 (使用 lambda 表达式)
    function<void(int)> preorder = [&](int u) { 
        traversal.push_back(u); // 1. 访问根结点 u
        // 2. 按排序后的顺序递归访问子结点 v
        for (int v : adj[u]) { 
            preorder(v);
        }
    };

    preorder(root); // 从根结点开始进行前序遍历

    // 输出第二行：前序遍历序列
    for (size_t i = 0; i < traversal.size(); i++) {
        if (i > 0) cout << " "; // 在数字之间输出空格
        cout << traversal[i]; // 输出当前结点编号
    }
    cout << "\n"; // 输出换行符

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