CF862B Mahmoud and Ehab and the bipartiteness

Mahmoud 和 Ehab 的冒险仍在继续！众所周知，在邪恶之地，Dr. Evil 喜欢二分图，尤其喜欢树。 一棵树是一个连通且无环的图。二分图是指可以将所有顶点划分为 $2$ 个集合，使得对于每条属于该图的边 $(u,v)$，$u$ 和 $v$ 属于不同的集合。更形式化的树和二分图定义可见下文注释部分。 Dr. Evil 给了 Mahmoud 和 Ehab 一棵包含 $n$ 个节点的树，并要求他们往这棵树中添加若干条边，使得添加完之后，图依然保持为二分图。此外，添加边后图需要保持简单（即图中不能有自环或重边）。你能求出他们最多可以添加多少条边吗？ 自环是指一条边的两个端点是同一个节点。简单图要求对于每一对节点，最多只有一个边连接它们。环和自环是不同的概念。

输入的第一行为一个整数 $n$，表示树的节点数（$1\leq n\leq 10^{5}$）。 接下来的 $n-1$ 行，每行为两个整数 $u$ 和 $v$（$1\leq u,v\leq n$，$u\neq v$），描述树中的一条边。 保证给定的图是一棵树。

输出一个整数，表示在满足条件的情况下，最多可以往树中添加多少条边。

树的定义：https://en.wikipedia.org/wiki/Tree_(graph_theory) 二分图的定义：[https://en.wikipedia.org/wiki/Bipartite_graph](https://en.wikipedia.org/wiki/Bipartite_graph) 在第一个测试样例中，唯一可以添加且不会出现自环或重边的边是 $(2,3)$，但添加这条边后，图将不再是二分图，因此答案为 $0$。 在第二个测试样例中，Mahmoud 和 Ehab 可以添加边 $(1,4)$ 和 $(2,5)$。 由 ChatGPT 5 翻译