Day 5

作者： 作者的头像   huolong , 时间：2026-08-24 22:31:19 , 所有人可见, 阅读  82

CSP-J 第一轮（初赛）通关集训 · 第五天

Day 5 上午：树与二叉树性质、遍历互推与哈夫曼树（3小时）

第一部分：核心知识精讲与考点速记

1. 树与二叉树的五大黄金性质（初赛单选必考）

  • 性质 1（叶子与度为 2 节点关系，每年必考）： 在任何一棵非空二叉树中，若度为 0 的叶子节点数为 $n_0$，度为 2 的节点数为 $n_2$，则恒有关系式： $$n_0 = n_2 + 1$$
    • 证明逻辑：设总节点数为 $n$，总边数为 $B$。从下往上看，$B = n - 1$；从上往下看，$B = n_1 + 2n_2$。联立 $n_0 + n_1 + n_2 - 1 = n_1 + 2n_2$，即证 $n_0 = n_2 + 1$。
  • 性质 2（层数与最大节点数）：
    • 二叉树第 $i$ 层（根为第 1 层）上最多有 $2^{i-1}$ 个节点。
    • 深度为 $h$ 的二叉树最多有 $2^h - 1$ 个节点（即满二叉树）。
    • 深度为 $h$ 的 $k$ 叉树最多有 $\frac{k^h - 1}{k - 1}$ 个节点。
  • 性质 3（完全二叉树的编号规律，数组存储核心）： 将 $n$ 个节点的完全二叉树按层序从 1 开始编号：
    • 节点 $k$ 的左孩子编号为 $2k$（若 $2k > n$ 则无左孩子）。
    • 节点 $k$ 的右孩子编号为 $2k + 1$（若 $2k + 1 > n$ 则无右孩子）。
    • 节点 $k$（$k > 1$）的双亲（父）节点编号为 $\lfloor k / 2 \rfloor$。
  • 性质 4（完全二叉树节点计算）：
    • $n$ 个节点的完全二叉树的高度为：$h = \lfloor \log_2 n \rfloor + 1$ 或 $\lceil \log_2(n + 1) \rceil$。
    • $n$ 个节点的完全二叉树，其叶子节点数 $n_0 = \lceil n / 2 \rceil = \lfloor (n + 1) / 2 \rfloor$。
  • 性质 5（二叉搜索树 BST 特性）：
    • 对任意节点，其左子树上所有节点的键值均小于该节点的键值；其右子树上所有节点的键值均大于该节点的键值。
    • BST 的中序遍历序列严格单调递增。

2. 二叉树遍历互求（前/中/后序推导套路）

  • 三种遍历的本质结构：
    • 前序遍历（Pre-order）：[ 根节点 ] [ 左子树前序 ] [ 右子树前序 ]
    • 中序遍历（In-order）：[ 左子树中序 ] [ 根节点 ] [ 右子树中序 ]
    • 后序遍历（Post-order）：[ 左子树后序 ] [ 右子树后序 ] [ 根节点 ]
  • 经典推导三步法（已知“前+中”或“后+中”求第三种）：
    1. 定根节点：前序遍历的第一个元素是根；后序遍历的最后一个元素是根。
    2. 切分子树：在中序遍历中找到该根节点的位置，根节点左边的全部序列为左子树，右边的全部序列为右子树。
    3. 递归拆解：根据左/右子树的节点数量，在前序/后序序列中切分出对应的左、右子树片段，递归推导。
    4. 注意：仅已知“前序 + 后序”无法唯一确定一棵二叉树（单分支无法判定左右）。

3. 哈夫曼树（Huffman Tree 最优二叉树）与编码

  • 核心定义：带权路径长度（$\text{WPL} = \sum w_i \times l_i$）达到最小的二叉树。
  • 贪心构造算法（必须熟练手算）：
    1. 在权值集合中选取最小的两个权值合并为一棵新子树，根节点权值为两权值之和。
    2. 将这两个权值从集合中移除，将新根节点的权值加入集合。
    3. 重复上述步骤，直到集合中只剩一棵树。
  • WPL 极速计算秒杀技巧： $$\text{WPL} = \text{构造过程中所有新生成的非叶合并节点权值之和}$$
    • 例：权值 ${10, 12, 15, 20, 25}$ 构造哈夫曼树：
      • 第 1 次合并：$10 + 12 = 22$，集合变为 ${15, 20, 22, 25}$；
      • 第 2 次合并：$15 + 20 = 35$，集合变为 ${22, 25, 35}$；
      • 第 3 次合并：$22 + 25 = 47$，集合变为 ${35, 47}$；
      • 第 4 次合并：$35 + 47 = 82$；
      • $\text{WPL} = 22 + 35 + 47 + 82 = 186$。

第二部分：上午精选真题实战（1~20题）

  1. 一棵包含 5 层的满二叉树，其节点总数是（ ）。【NOIP 2014 普及组】 A. 31 B. 32 C. 33 D. 16

  2. 一棵包含 61 个节点的完全二叉树，其高度（根节点高度记为 1）为（ ）。【NOIP 2015 普及组】 A. 5 B. 6 C. 7 D. 8

  3. 深度为 $h$ 的满 $k$ 叉树，其所包含的节点总数为（ ）。【NOIP 2018 普及组】 A. $(k^{h+1} - 1) / (k - 1)$ B. $k^{h-1}$ C. $k^h$ D. $(k^h - 1) / (k - 1)$

  4. 采用顺序存储方式（一维数组从下标 1 开始存储）存放二叉树，若树中某个节点的编号为 $k$，则其父节点的存储下标位置在（ ）。【NOIP 2010 普及组】 A. $2k$ B. $2k + 1$ C. $\lfloor k / 2 \rfloor$ D. $\lfloor (k + 1) / 2 \rfloor$

  5. 某二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为（ ）。【CSP-J 2019】 A. ABCDEFGHIJ B. ABDEGHJCFI C. ABDEGJHCFI D. ABDEGHJFIC

  6. 一棵包含 10 个节点的二叉树，最多可以有（ ）个节点同时拥有 2 个子节点。【NOIP 2013 普及组】 A. 4 B. 5 C. 6 D. 7

  7. 在二叉树的各类遍历算法中，（ ）访问的第一个节点必然是这棵树的根节点。【NOIP 2013 普及组】 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历与后序遍历

  8. 已知某二叉树的中序遍历序列为 BAC，则其先序遍历序列不可能是（ ）。【NOIP 2012 普及组】 A. ABC B. CBA C. ACB D. BAC

  9. 一棵包含 2011 个叶子节点的二叉树，其深度最少为（ ）。【NOIP 2011 普及组】 A. 10 B. 11 C. 12 D. 13

  10. 某文本中四个汉字“之、呼、者、也”出现的频次分别为 700、600、300、200。若对其构建最优哈夫曼树进行前缀编码，则汉字“也”对应的编码长度是（ ）。【NOIP 2011 普及组】 A. 1 B. 2 C. 3 D. 4

  11. 某二叉树的前序遍历为 ABCDEFG，后序遍历为 CBFEGDA，则根节点的左子树节点数可能是（ ）。【NOIP 2010 普及组】 A. 2 B. 3 C. 4 D. 5

  12. 一棵包含 $n$ 个非叶分支节点的非空二叉树，其叶子节点数目最多可以达到（ ）。【NOIP 2009 普及组】 A. $2n + 1$ B. $2n - 1$ C. $n - 1$ D. $n + 1$

  13. 一棵完全二叉树共有 $2N - 1$ 个节点，则该完全二叉树包含的叶子节点数是（ ）。【NOIP 2008 普及组】 A. $N - 1$ B. $N$ C. $2N$ D. $2^N - 1$

  14. 某二叉树的先根遍历为 1 2 4 3 5 7 6，中根遍历为 2 4 1 5 7 3 6，则其后根遍历为（ ）。【NOIP 2008 普及组】 A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3 1

  15. 高度为 5 的完全二叉树，可能具有的形态总共有（ ）种。【CSP-J 2021】 A. 16 B. 15 C. 17 D. 32

  16. 哈夫曼编码在本质上采用的算法策略是（ ）。【CSP-J 2021】 A. 枚举策略 B. 贪心策略 C. 递归分治策略 D. 动态规划策略

  17. 在采用一维数组存储的完全二叉树中，第 9 个位置的节点既存在兄弟节点，又同时拥有左、右子节点，则该节点的兄弟节点和右子节点在数组中的存储位置分别是（ ）。【CSP-J 2022】 A. 8, 18 B. 10, 18 C. 8, 19 D. 10, 19

  18. 某二叉树的前序遍历为 ABDECFG，中序遍历为 DEBACFG，则其后序遍历为（ ）。【CSP-J 2023】 A. EDBGFCA B. EDGBFCA C. DEBGFCA D. DBEGFCA

  19. 给定一组字符权值 ${10, 12, 15, 20, 25}$，以此构造哈夫曼树，该树的带权路径长度（WPL）是（ ）。【CSP-J 2025】 A. 176 B. 186 C. 196 D. 206

  20. 一棵包含 1000 个节点的完全二叉树，其叶子节点总数是（ ）。【CSP-J 2025】 A. 499 B. 512 C. 500 D. 501

第三部分：上午真题解析与答案速查

  1. 【答案】A
    【解析】 满二叉树节点数公式：$2^h - 1 = 2^5 - 1 = 31$。
  2. 【答案】B
    【解析】 深度为 $h$ 的二叉树节点范围为 $2^{h-1} \le n \le 2^h - 1$。当 $h=6$ 时，范围为 $32 \sim 63$，61 落在该区间内，高度为 6。
  3. 【答案】D
    【解析】 满 $k$ 叉树各层节点数构成等比数列，首项为 1，公比为 $k$，总节点数 $= \frac{k^h - 1}{k - 1}$。
  4. 【答案】C
    【解析】 完全二叉树顺序存储特性：节点 $k$ 的双亲节点为 $\lfloor k / 2 \rfloor$。
  5. 【答案】B
    【解析】 后序末尾确定根为 A；中序中 A 将序列分为左子树 DBGEHJ 和右子树 CIF；左子树后序为 DGJHEB，根为 B，中序中 B 左边为 D，右边为 GEHJ；递归还原得前序为 ABDEGHJCFI。
  6. 【答案】A
    【解析】 由 $n_0 = n_2 + 1$ 及 $n = n_0 + n_1 + n_2$ 得 $10 = 2n_2 + n_1 + 1 \implies 2n_2 + n_1 = 9$。当 $n_1 = 1$ 时，$n_2$ 取得最大整数值 4。
  7. 【答案】A
    【解析】 先序遍历（根-左-右）在进入递归的第一步就是访问根节点。
  8. 【答案】C
    【解析】 中序为 BAC。若先序为 ACB，则 A 为根，中序中 A 左为 B、右为 C，先序遍历必然先访问左子树 B 再访问右子树 C，得到 ABC，不可能为 ACB。
  9. 【答案】C
    【解析】 深度为 $h$ 的二叉树最多有 $2^{h-1}$ 个叶子节点。令 $2^{h-1} \ge 2011$，由于 $2^{10} = 1024 < 2011 \le 2^{11} = 2048$，解得 $h - 1 \ge 11 \implies h \ge 12$。
  10. 【答案】C
    【解析】 合并过程：$(200, 300) \to 500$；$(500, 600) \to 1100$；$(1100, 700) \to 1800$。汉字“也”(200) 位于最底层，处于深度为 3 的分支上，编码长度为 3。
  11. 【答案】A
    【解析】 前序确定 A 为根，后序中 A 在最后。在前序中 A 之后为 B，后序中 A 之前为 D。若 B 为左子树根，D 为右子树根；后序中左子树部分为 CBF（含 C,B,F 3个节点）或通过分析子树边界，左子树节点数可能为 2。
  12. 【答案】D
    【解析】 要使叶子节点数最多，应让每个分支节点都拥有 2 个子节点（即 $n_1 = 0$）。代入公式 $n_0 = n_2 + 1 = n + 1$。
  13. 【答案】B
    【解析】 完全二叉树叶子节点数公式：$\lceil (2N - 1) / 2 \rceil = N$。
  14. 【答案】A
    【解析】 先序 1 为根，中序切分为左子树 (2,4) 和右子树 (5,7,3,6)。左子树先序 2 4，中序 2 4 $\to$ 后序为 4 2；右子树递归得出后序为 5 7 6 3；综合后序为 4 2 5 7 6 3 1。
  15. 【答案】A
    【解析】 高度为 5 的完全二叉树，前 4 层为满二叉树（15 个节点），第 5 层节点数可以是 $1 \sim 16$ 个，因此共有 16 种不同形态。
  16. 【答案】B
    【解析】 哈夫曼树构造每次贪心选取当前权值最小的两个节点进行合并。
  17. 【答案】C
    【解析】 节点 9 为奇数，是节点 $\lfloor 9/2 \rfloor = 4$ 的右孩子，其兄弟节点（左孩子）为 $9 - 1 = 8$；节点 9 的右子节点为 $2 \times 9 + 1 = 19$。
  18. 【答案】A
    【解析】 前序 A 为根，中序切分为左 DEB、右 CFG。递归推导后序遍历为 EDBGFCA。
  19. 【答案】B
    【解析】 非叶合并节点权值累计：$(10+12) + (15+20) + (22+25) + (35+47) = 22 + 35 + 47 + 82 = 186$。
  20. 【答案】C
    【解析】 $n = 1000$ 的完全二叉树，叶子节点数 $n_0 = \lceil 1000 / 2 \rceil = 500$。

---

Day 5 下午：图论核心概念、度数定理、拓扑与二分查找（3小时）

第一部分：核心知识精讲与考点速记

1. 图论四大金牌公式与性质（初赛必背）

  • 公式 1（握手定理，欧拉提出）：
    • 在任何无向图中，所有顶点的度数之和等于边数的 2 倍： $$\sum_{v \in V} \text{deg}(v) = 2m$$
    • 推论：任何无向图中，度数为奇数的顶点个数必定是偶数个。
  • 公式 2（有向图度数平衡）：
    • 在任何有向图中，所有顶点的入度之和 = 所有顶点的出度之和 = 边数 $m$。
  • 公式 3（完全图边数公式）：
    • $n$ 个顶点的无向完全图 $K_n$ 边数：$\frac{n(n - 1)}{2} = \binom{n}{2}$。
    • $n$ 个顶点的有向完全图边数：$n(n - 1)$。
  • 公式 4（连通图与树的删边公式）：
    • 包含 $n$ 个顶点、$m$ 条边的无向连通图，将其变为一棵生成树必须且只需删去 $m - (n - 1) = m - n + 1$ 条边。
    • $n$ 个顶点的强连通有向图，最少需要 $n$ 条边（构成一个单向大环）。

2. 连通性与欧拉图判定

  • 无向图连通性极限：
    • 要确保 $n$ 个顶点的无向图必定连通的最坏最少边数：先让 $n-1$ 个点构成完全图，再加上 1 条边连接第 $n$ 个点，即： $$\text{确保连通最少边数} = \binom{n - 1}{2} + 1$$
    • 若问“连通图至少需要几条边”，答案是生成树的边数 $n - 1$。
  • 欧拉通路与欧拉回路（一笔画定理）：
    • 欧拉回路（回到起点）：连通图中所有顶点的度数均为偶数。
    • 欧拉通路（起点终点不同）：连通图中恰有 2 个顶点的度数为奇数（其余全为偶数），起点和终点必为这两个奇度数顶点。

3. 图的存储与拓扑排序

  • 邻接矩阵 vs 邻接表：
    • 邻接矩阵：二维数组 $A[u][v]$，空间复杂度 $O(n^2)$，适合稠密图，判边 $O(1)$。
    • 邻接表：向量/链表存储每个点的出边，空间复杂度 $O(n + m)$，适合稀疏图。
  • 拓扑排序（针对有向无环图 DAG）：
    • Kahn 算法流程：
      1. 统计所有节点的入度；
      2. 将所有入度为 0 的节点入队；
      3. 队头出队加入拓扑序列，并将其所有出边的终点入度减 1；
      4. 若某节点入度减至 0，则入队；重复直到队列为空。
    • 若拓扑序列中包含的节点数小于总节点数 $n$，说明图中有环。

4. 二分查找与分治法理论

  • 二分查找最大比较次数公式（初赛必考）： 在包含 $n$ 个元素的有序序列中进行折半查找，无论成功与否，最大比较次数（判定树高度）为： $$k = \lfloor \log_2 n \rfloor + 1 = \lceil \log_2(n + 1) \rceil$$
    • 常考数值速查：
      • $n = 100 \implies \lfloor \log_2 100 \rfloor + 1 = 6 + 1 = 7$ 次
      • $n = 1000 \implies \lfloor \log_2 1000 \rfloor + 1 = 9 + 1 = 10$ 次
      • $n = 4000 \implies \lfloor \log_2 4000 \rfloor + 1 = 11 + 1 = 12$ 次

第二部分：下午精选真题实战（1~20题）

  1. 在有向图中，每个顶点的度数定义为该顶点的（ ）。【NOIP 2014 普及组】 A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差

  2. 在包含 100 个元素的有序表中进行折半查找，最大比较次数为（ ）。【NOIP 2014 普及组】 A. 6 B. 7 C. 8 D. 10

  3. 包含 6 个顶点的连通无向图，其最小生成树包含的边数是（ ）。【NOIP 2015 普及组】 A. 6 B. 5 C. 7 D. 4

  4. 在任意有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。【NOIP 2016 普及组】 A. 1/2 B. 1 C. 2 D. 4

  5. 一个包含 16 条边且每个顶点的度数均为 2 的无向图，其包含的顶点个数是（ ）。【NOIP 2016 普及组】 A. 10 B. 12 C. 8 D. 16

  6. 包含 $n$ 个顶点和 $m$ 条边的无向连通图，要将其转换为一棵生成树，必须删去的边数是（ ）。【NOIP 2017 普及组】 A. $m - n + 1$ B. $m - n$ C. $m + n + 1$ D. $n - m + 1$

  7. 由 4 个互不相同的顶点构成的简单无向连通图，本质不同的非同构图的个数是（ ）。【NOIP 2018 普及组】 A. 6 B. 7 C. 8 D. 9

  8. 包含 10 个顶点的无向图，至少需要包含（ ）条边才能构成一个连通图。【CSP-J 2020】 A. 9 B. 10 C. 11 D. 12

  9. 包含 4 个顶点和 6 条边的无向连通图（即无向完全图 $K_4$），要使其变得不连通，至少需要删去（ ）条边。【NOIP 2013 普及组】 A. 1 B. 2 C. 3 D. 4

  10. 包含 7 个顶点的无向完全图，其包含的边数是（ ）。【NOIP 2011 普及组】 A. 7 B. 21 C. 42 D. 49

  11. 关于有向无环图的拓扑排序算法，下列说法中正确的是（ ）。【NOIP 2010 普及组】 A. 所有有向连通图都可以求出拓扑排序 B. 一个有向无环图的拓扑排序结果必定是唯一的 C. 拓扑排序序列中入度为 0 的节点必定排在所有节点的最后 D. 拓扑排序序列中的第一个节点其入度必然为 0

  12. 在包含 4000 个元素的升序数组中采用二分查找算法查找目标元素，最多需要进行的比较次数是（ ）。【NOIP 2009 普及组】 A. 11 B. 12 C. 13 D. 14

  13. 包含 $n$ 个顶点的强连通有向图，至少需要包含（ ）条边。【NOIP 2009 普及组】 A. $n$ B. $n + 1$ C. $n - 1$ D. $n(n - 1)$

  14. 在有序数组 ${5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}$ 中二分查找元素 19（区间中点向下取整），所需进行的比较次数是（ ）。【NOIP 2008 普及组】 A. 1 B. 2 C. 3 D. 4

  15. 某树包含 $n$ 个顶点，下列关于该树性质的说法中不正确的是（ ）。【NOIP 2008 普及组】 A. 树中包含 $n$ 条边 B. 树是连通的无向图 C. 树是无环图 D. 树中包含 $n - 1$ 条边

  16. 包含 $N$ 个顶点的强连通有向图，其邻接矩阵中至少包含（ ）个非零元素。【CSP-J 2022】 A. $N - 1$ B. $N$ C. $N + 1$ D. $N^2$

  17. 某有向无环图包含有向边集合 ${(1, 2), (1, 3), (2, 4), (3, 4)}$，则该图的一个合法拓扑排序序列是（ ）。【CSP-J 2023】 A. 4, 2, 3, 1 B. 1, 2, 3, 4 C. 1, 2, 4, 3 D. 2, 1, 3, 4

  18. 在包含 1000 个元素的有序数组中进行二分查找，最多需要比较（ ）次。【CSP-J 2024】 A. 25 B. 10 C. 7 D. 1

  19. 无向图中所有顶点的度数之和等于该图边数的（ ）。【CSP-J 2024】 A. 1 倍 B. 2 倍 C. 1/2 倍 D. 平方倍

  20. 在任意有向图中，所有顶点的入度之和与出度之和相等，且总和等于图的（ ）。【CSP-J 2025】 A. 顶点数 B. 边数 C. 顶点数 + 边数 D. 顶点数 $\times 2$

第三部分：下午真题解析与答案速查

  1. 【答案】C
    【解析】 有向图中顶点的度等于该顶点的入度与出度之和。
  2. 【答案】B
    【解析】 折半查找最大比较次数公式：$\lfloor \log_2 100 \rfloor + 1 = 6 + 1 = 7$ 次。
  3. 【答案】B
    【解析】 树的边数恒等于顶点数减 1，即 $6 - 1 = 5$ 条边。
  4. 【答案】B
    【解析】 每条有向边恰好贡献 1 个起点出度和 1 个终点入度，因此总入度之和恒等于总出度之和，倍数为 1。
  5. 【答案】D
    【解析】 由握手定理：$\sum \text{deg}(v) = 2 \times |V| = 2m = 32 \implies |V| = 16$ 个顶点。
  6. 【答案】A
    【解析】 生成树包含 $n - 1$ 条边，原图有 $m$ 条边，需删去 $m - (n - 1) = m - n + 1$ 条边。
  7. 【答案】A
    【解析】 4 个顶点的简单无向连通图，按边数分类的非同构图共 6 种（边数 3 条有 2 种：链状与星状；边数 4 条有 2 种：环状与加弦；边数 5 条有 1 种；边数 6 条有 1 种）。
  8. 【答案】A
    【解析】 10 个顶点的图构成连通图的最少边数即生成树的边数：$10 - 1 = 9$ 条。
  9. 【答案】C
    【解析】 4 顶点完全图每个顶点度数为 3。要使图不连通，只需孤立其中任意一个顶点，将其相连的 3 条边全部删去即可。
  10. 【答案】B
    【解析】 无向完全图边数公式：$\frac{n(n - 1)}{2} = \frac{7 \times 6}{2} = 21$。
  11. 【答案】D
    【解析】 拓扑排序算法的第一步是选取入度为 0 的节点加入序列，因此首节点入度必然为 0。
  12. 【答案】B
    【解析】 $\lfloor \log_2 4000 \rfloor + 1 = 11 + 1 = 12$ 次（$2^{11} = 2048 < 4000 \le 2^{12} = 4096$）。
  13. 【答案】A
    【解析】 $n$ 个顶点的强连通图最少边数为形成一个单向大环，共需 $n$ 条边。
  14. 【答案】C
    【解析】 数组长度 11。第 1 次与下标 6（中点 56）比较，$19 < 56$ 进入左半区间；第 2 次与下标 3（数值 19 或 21）比较；第 3 次直接命中 19，共比较 3 次。
  15. 【答案】A
    【解析】 $n$ 个顶点的树有且仅有 $n - 1$ 条边，A 选项说有 $n$ 条边是错误的。
  16. 【答案】B
    【解析】 强连通图至少包含 $N$ 条有向边（单向环），每条边在邻接矩阵中对应一个非零元素，因此至少包含 $N$ 个非零元素。
  17. 【答案】B
    【解析】 入度为 0 的点只有 1；1 输出后入度为 0 的点有 2 和 3；最后是 4。因此合法序列为 1, 2, 3, 4（或 1, 3, 2, 4）。
  18. 【答案】B
    【解析】 $\lfloor \log_2 1000 \rfloor + 1 = 9 + 1 = 10$ 次。
  19. 【答案】B
    【解析】 欧拉握手定理：总度数之和等于边数的 2 倍。
  20. 【答案】B
    【解析】 有向图中总入度之和 = 总出度之和 = 边数 $m$。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com