题解
根据二分图的性质，我们知道如果将树的根节点划分到第一个阵营，那么它的子节点必须划分到第二个阵营；如果根节点划分到第二个阵营，那么它的子节点必须划分到第一个阵营。
所以我们可以用dfs来遍历树去计算属于第一个阵营的节点个数，然后用总节点数减去属于第一个阵营的节点个数就是属于第二个阵营的节点个数，然后用第一个阵营的节点个数乘以第二个阵营的节点个数减去古路的数量就是可以新建的道路数量。
AC代码
n = int(input())
题目内容
在一个王国有 n 座城市，由 n−1 条古路连接，形成一个树状结构。国王希望新修一些双向道路，但要求整个道路网络是“和谐”的：可以将所有城市划分为两个阵营，使得每条道路连接的城市恰好分属不同阵营。已知古路已经满足这一要求。请问，最多能够新建多少条双向道路？
城市个数 n 满足 2≤n≤ 10^5。
输入描述
第一行包含一个整数 n，表示城市数量。
接下来 n−1 行，每行包含两个整数 u 和 v，表示一条古路所连接的两个城市编号，城市编号从 1 到 n。
