问题描述

题解

根据二分图的性质，我们知道如果树的根是红色的，那么它的子节点必须是黑色的，如果根是黑色的，那么它的子节点必须是红色的。 所以我们可以用dfs来遍历树去计算红色节点的个数，然后用总节点数减去红色节点的个数就是黑色节点的个数，然后用红色节点的个数乘以黑色节点的个数减去边的个数就是可以加的边的个数。

AC代码

• Pyton

n = int(input())
# 初始化邻接表