C++ 树形结构 k叉树最优根节点选择问题

参考资料

问题描述

题目背景

对于一棵有根树，如果它的全部节点都满足：孩子个数不多于 k，且 k 是所有可取的值中最小的那个，则称它是一个 k 叉树。

形式化的，记 cnt_i 为有根树上，第 i 个节点的孩子数目，则：

k = max{cnt_1, cnt_2, ..., cnt_n}

现在智乃想要给一棵由 n 个节点构成的无根树标记一个根节点，她发现选择的根节点不同时，k 的值也不同。

任务：选择一个节点作为根节点，以最小化 k 的取值，并输出最小的 k 值和对应的根节点编号（多个时选编号最小的）。

输入格式

  • 第一行：一个正整数 n (2 ≤ n ≤ 10^5)，代表树的节点数量
  • 接下来 n-1 行：每行两个正整数 u_i, v_i，代表无根树上的一条无向边

输出格式

输出两个正整数：最小的 k 值和对应的根节点编号

示例

示例 1：

输入：
4
3 1
2 3
3 4

输出：
2 1

示例 2：

输入：
3
1 2
1 3

输出：
1 2

问题分析

核心观察

在理解这道题之前，我们需要明确几个关键概念：

  1. 无根树与有根树的区别

    • 无根树：所有节点地位平等，边是无向的
    • 有根树：指定一个根节点后，其他节点按层次组织，边有方向（父→子）

  2. 度数的定义

    • 在无根树中，节点的度数 = 连接该节点的边数
    • 在有根树中，节点的孩子数取决于它是否为根节点

  3. 根节点对 k 值的影响

    当我们选择节点 r 作为根时：

    • 根节点 r 的孩子数 = degree[r]（所有连接的边都指向孩子）
    • 非根节点 u 的孩子数 = degree[u] - 1（有一条边连向父节点）

    因此：

    k_r = max(degree[r], max{degree[u] - 1 | u ≠ r})

问题转化

设：

  • max_deg = 所有节点中的最大度数
  • second_max_deg = 次大度数

对于节点 r，我们可以分情况讨论：

情况 1：degree[r] < max_deg

k_r = max(degree[r], max_deg - 1)

因为最大度数节点不是根，它会损失一个孩子。

情况 2：degree[r] == max_deg

  • 如果只有 r 一个节点有最大度数：
    k_r = max(max_deg, second_max_deg - 1)
  • 如果有多个节点有最大度数：
    k_r = max_deg

最优策略

通过上述分析，我们发现：

  • 选择度数最大的节点作为根，通常能获得较小的 k 值
  • 但需要考虑次大度数的影响

解题思路

算法流程

1. 统计每个节点的度数
2. 找出最大度数 max_deg 和次大度数 second_max_deg
3. 统计有多少个节点的度数等于 max_deg
4. 对每个节点 r，根据公式计算 k_r
5. 选择 k_r 最小的节点（相同时选编号最小的）

伪代码

输入 n 和 n-1 条边
初始化 degree 数组

for 每条边 (u, v):
    degree[u]++
    degree[v]++

找出 max_deg, second_max_deg, max_count

for r from 1 to n:
    if degree[r] < max_deg:
        k_r = max(degree[r], max_deg - 1)
    else if degree[r] == max_deg:
        if max_count == 1:
            k_r = max(max_deg, second_max_deg - 1)
        else:
            k_r = max_deg
    
    更新最优答案

输出 min_k 和 best_root

代码实现

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    vector<int> degree(n + 1, 0);
    
    // 读入边并统计度数
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        degree[u]++;
        degree[v]++;
    }
    
    // 找出最大度数和次大度数
    int max_deg = 0, second_max_deg = 0;
    int max_count = 0; // 有多少个节点的度数等于max_deg
    
    for (int i = 1; i <= n; i++) {
        if (degree[i] > max_deg) {
            second_max_deg = max_deg;
            max_deg = degree[i];
            max_count = 1;
        } else if (degree[i] == max_deg) {
            max_count++;
        } else if (degree[i] > second_max_deg) {
            second_max_deg = degree[i];
        }
    }
    
    // 计算每个节点作为根时的k值
    int min_k = INT_MAX;
    int best_root = 1;
    
    for (int r = 1; r <= n; r++) {
        int k_r;
        
        if (degree[r] < max_deg) {
            // r不是最大度数节点
            k_r = max(degree[r], max_deg - 1);
        } else {
            // degree[r] == max_deg
            if (max_count == 1) {
                // r是唯一的最大度数节点
                k_r = max(max_deg, second_max_deg - 1);
            } else {
                // 有多个最大度数节点
                k_r = max_deg;
            }
        }
        
        // 更新最优答案（k值小的优先，相同时编号小的优先）
        if (k_r < min_k || (k_r == min_k && r < best_root)) {
            min_k = k_r;
            best_root = r;
        }
    }
    
    cout << min_k << " " << best_root << endl;
    
    return 0;
}

代码说明

关键变量：

  • degree[i]：节点 i 的度数
  • max_deg：所有节点中的最大度数
  • second_max_deg：次大度数
  • max_count：度数等于最大度数的节点数量

核心逻辑：

  1. 度数统计（第 10-16 行）：遍历所有边，统计每个节点的度数
  2. 找最大值和次大值（第 18-31 行）：一次遍历找出最大和次大度数
  3. 计算 k 值（第 33-52 行）：根据节点度数与最大度数的关系计算 k_r
  4. 更新答案（第 54-57 行）：保持最小 k 值和最小编号

示例验证

示例 1 详解

输入：

4
3 1
2 3
3 4

树的结构（无根树）：

1
|
3---2
|
4

度数统计：

  • degree[1] = 1
  • degree[2] = 1
  • degree[3] = 3 ← 最大度数
  • degree[4] = 1

各节点作为根时的 k 值：

根节点 degree[r] 计算公式 k_r 说明
1 1 max(1, 3-1) 2 节点3有2个孩子
2 1 max(1, 3-1) 2 节点3有2个孩子
3 3 max(3, 1-1) 3 节点3本身有3个孩子
4 1 max(1, 3-1) 2 节点3有2个孩子

结论： min_k = 2，最小编号 = 1，输出 2 1 ✓

示例 2 详解

输入：

3
1 2
1 3

树的结构：

2
 \
  1
 /
3

度数统计：

  • degree[1] = 2 ← 最大度数
  • degree[2] = 1
  • degree[3] = 1

各节点作为根时的 k 值：

根节点 degree[r] 计算公式 k_r 说明
1 2 max(2, 1-1) 2 节点1有2个孩子
2 1 max(1, 2-1) 1 节点1只有1个孩子了
3 1 max(1, 2-1) 1 节点1只有1个孩子了

结论： min_k = 1，最小编号 = 2，输出 1 2 ✓

复杂度分析

时间复杂度

  • 读入边并统计度数：O(n)
  • 找最大和次大度数：O(n)
  • 枚举所有节点计算 k 值：O(n)

总时间复杂度：O(n)

空间复杂度

  • degree 数组：O(n)
  • 其他变量：O(1)

总空间复杂度：O(n)

优化点

本算法已经是最优解，无需进一步优化：

  • 不需要真正建立树结构
  • 不需要 DFS/BFS 遍历
  • 只需统计度数即可得出答案

扩展思考

变体问题

  1. 如果要输出所有最优根节点怎么办？

    • 使用 vector 存储所有 k 值等于 min_k 的节点

  2. 如果树的节点数达到 10^6 级别？

    • 当前算法依然高效，O(n) 可以轻松处理

  3. 如果要求输出构造后的树结构？

    • 需要真正建图并进行 DFS/BFS，复杂度仍为 O(n)

相关问题

总结

核心知识点

  1. ⭐ 度数是关键：无需建树，只需统计度数
  2. ⭐ 公式推导：根节点与非根节点的孩子数计算方式不同
  3. ⭐ 分类讨论：根据节点度数与最大度数的关系分情况处理
  4. ⭐ 贪心思想：选择度数大的节点作为根通常更优

易错点

  • ❌ 忘记处理多个节点有相同最大度数的情况
  • ❌ 没有正确计算次大度数
  • ❌ 输出时忘记优先选择编号小的节点
  • ❌ 边界情况：链状树（退化为 1 叉树）

学习建议

  • 理解无根树与有根树的转换关系
  • 掌握度数的概念和应用
  • 学会用数学公式简化树形问题
  • 多做树形结构相关的题目

参考代码模板

// 树形问题通用模板
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    vector<int> degree(n + 1, 0);
    
    // 1. 统计度数
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        degree[u]++;
        degree[v]++;
    }
    
    // 2. 找极值
    int max_deg = *max_element(degree.begin() + 1, degree.end());
    
    // 3. 枚举计算
    int ans = INT_MAX;
    int pos = 1;
    for (int i = 1; i <= n; i++) {
        int cur = /* 根据问题计算 */;
        if (cur < ans || (cur == ans && i < pos)) {
            ans = cur;
            pos = i;
        }
    }
    
    cout << ans << " " << pos << endl;
    
    return 0;
}