为使树保持二分图，需要添加的最大边数

目标是通过添加尽可能多的边将 N 节点树转换为二分图。

请记住，不允许自环和多重边，但允许环。

图解

解释： 可以添加连接节点 3 和 4 的边以使图保持二分图。

只能向图中添加一条边使其成为二分图。

解释： 即使添加两条边 (3, 4) 和 (3, 5)，图仍保持二分图。

简单方法

该问题的基本解决方案如下

树中的每个节点都应着色，从而在黑色节点和白色节点之间建立连接（树始终是二分图，因此始终存在这种配置）。

然后，对于每一对可行的节点，确定是否可以在它们之间添加边。

要将上述思想付诸实施，请遵循以下步骤

• 首先，遍历树，为每个节点分配黑色或白色，以便每条边连接一个黑色节点和一个白色节点。（所有树都是二分图。）
• 通过遍历所有节点对来检查是否可以在它们之间添加边。
• 如果节点颜色不同且它们之间没有边，则可以添加一条边。因此，增加计数。
• 没有其他方法可以添加边。
• 答案是计数的总值。

上述方法以下列方式实现。

C++ 程序

输出

1

• 时间复杂度将为 O(N²)。
• 辅助空间将为 O(N²)。

高效方法

通过以下观察可以减少上述方法所需的时间

• 假设树最初有 B 个黑色节点和 W 个白色节点。因此，由这些节点构建的二分图最多可以有 B*W 条边。
• 因此，对于 N 个节点，可以添加到树中的最大边数为 B*W - (N-1) [因为有 N 个节点的树有 N-1 条边]。

请遵循以下说明

• 首先，遍历树，为每个节点分配黑色或白色，以便每条边连接一个黑色节点和一个白色节点。（所有树都是二分图。）
• 确定黑色和白色节点的数量。
• 使用根据上述观察得出的公式确定可以添加的最大边数。

上述方法以下列方式实现。

C++ 程序

输出

1

• 时间复杂度将为 O(N)。
• 辅助空间将为 O(N)。