B. Mahmoud 和 Ehab 与二分图 详细题解

题目核心理解

给定一棵 $n$ 个节点的树，树本身是二分图，可以把所有点分成两个部分。 你可以向图中加边，要求：

1. 加边后仍然是二分图；
2. 图是简单图（无自环、无重边）。

求最多能添加多少条边。

数据范围：

• $1\le n\le 10^5$

核心思路

1. 关键性质

• 树一定是二分图，可以用黑白染色分成两个集合，设大小分别为 $l$ 和 $r$。
• 二分图的最大可能边数是两个集合之间的完全匹配：$l\times r$。
• 树本身已经占用了 $n-1$ 条边。
• 能添加的边数 = 最大边数 − 已有边数。

2. 计算规则

答案直接由两个集合大小得出：

3. 求解方式

对树做一次 BFS / DFS 进行二分染色，统计两种颜色的节点数量 $l$ 和 $r$。

算法流程

1. 读入树，用邻接表存储。
2. 从任意节点开始进行黑白染色（DFS 或 BFS）。
3. 统计黑色节点数 $l$、白色节点数 $r$。
4. 用公式 $l\times r-(n-1)$ 计算答案并输出。

公式与复杂度分析

最终答案公式：

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

可在线性时间内处理 $n\le 10^5$ 的数据，完全满足题目限制。