小O有一棵 n 个点组成的树，树上的点从 1 到 n 编号，树上的边是无向的。任意一棵树都是二分图，小O想知道她最多可以给树加多少条边，使得新的图仍然是二分图。 二分图的定义：如果一个图的所有点可以被分成两个集合 A 和 B ，使得所有的边都是一端在 A 中，一端在 B 中，那么这个图就是二分图。
第一行输入一个整数 n(1 ≤ n ≤ 10^5 ) ，表示树上的点数。 此后 n-1 行，第 i 行输入两个整数 u_i 和 v_i(1 ≤ u_i, v_i ≤ n ) ，表示树上的一条边连接了点 u_i 和点 v_i 。保证这些边可以形成一棵树。
在一行上输出一个正整数，表示最多可以给树加多少条边，使得新的图仍然是二分图。
4 1 2 2 3 3 4
1
考点：树 · 图 · 广度优先搜索(BFS)
数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
推荐方向：树
树结构上的遍历（DFS 求子树信息 / BFS 求层序），多数树题是「后序遍历 + 回溯」。
思路框架（树 通法 · 非本题专属）
实现要点：递归深度可能到 1e5，注意递归爆栈；必要时改迭代或调整递归深度。
复杂度：时间 O(n) ｜ 空间 O(n)
该范式的通法易错点
对照本题
样例 1：输入 4 / 1 2 / 2 3 / 3 4 → 输出 1
可以添加一条边 (1, 4)，新的图仍然是二分图。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2024年秋招-OPPO-AI/算法岗笔试。