小O的树上加边

OPPO 笔试真题 · 2024 秋招 · AI/算法岗

判题请到牛客原题提交。

题目描述

小O有一棵 $n$ 个点组成的树，树上的点从 $1$ 到 $n$ 编号，树上的边是无向的。任意一棵树都是二分图，小O想知道她最多可以给树加多少条边，使得新的图仍然是二分图。

二分图的定义：如果一个图的所有点可以被分成两个集合 $A$ 和 $B$，使得所有的边都是一端在 $A$ 中，一端在 $B$ 中，那么这个图就是二分图。

输入格式

第一行输入一个整数 $n\ (1 \leq n \leq 10^5 )$，表示树上的点数。

此后 $n-1$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i\ (1 \leq u_i, v_i \leq n )$，表示树上的一条边连接了点 $u_i$ 和点 $v_i$。保证这些边可以形成一棵树。

输出格式

在一行上输出一个正整数，表示最多可以给树加多少条边，使得新的图仍然是二分图。

示例

示例 1

输入：

4
1 2
2 3
3 4

输出：

1

说明：

可以添加一条边 (1, 4)，新的图仍然是二分图。

---

解题思路

第一步：树天生就是二分图

从任意一个点出发交替染两种颜色（黑 / 白），因为树上没有环，永远走不到冲突，
所以树一定是二分图。而且树是连通的，染色方案唯一：一旦 1 号点的颜色确定，
其它每个点的颜色就被到 1 号点的距离奇偶性钉死了，只存在「黑白互换」这种等价写法。
两类点的数量 c0、c1 因此是固定的。

第二步：加边后仍是二分图意味着什么

新图要保持二分图，就必须存在一种二分划分使所有边都跨色。但树的边已经把
划分定死了（第一步），所以新加的每条边也只能连接「一个黑点 + 一个白点」。
一旦连了两个同色点，它们与树上的路径就构成一个奇环，图不再是二分图。

第三步：最多能加多少条

在「所有边都跨色」这个约束下，边的数量上限就是完全二分图：

c0 * c1

（每个黑点与每个白点之间各有一条边。）这个上限是能达到的：把所有还没连上的
黑白对全部补上，得到的正是完全二分图，它当然是二分图。

树本身已经有 n - 1 条边（全都在这个完全二分图里），所以答案就是

c0 * c1 - (n - 1)

第四步：统计两类点数

从 1 号点出发 BFS，边拓展边染色，同时把两种颜色的点数累计起来。
用 BFS 而不是递归 DFS，是因为 n = 10^5 的链会让递归栈溢出。

---

完整代码实现

import sys
from collections import deque


def solve() -> None:
    """BFS 染色统计两类点数，再算完全二分图的边数"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    n = int(data[0])
    adj = [[] for _ in range(n + 1)]
    idx = 1
    for _ in range(n - 1):
        u = int(data[idx])
        v = int(data[idx + 1])
        idx += 2
        adj[u].append(v)
        adj[v].append(u)

    color = [-1] * (n + 1)
    color[1] = 0
    cnt = [1, 0]                 # cnt[0] / cnt[1] 为两类点的数量

    dq = deque([1])
    while dq:
        u = dq.popleft()
        for w in adj[u]:
            if color[w] == -1:
                color[w] = color[u] ^ 1
                cnt[color[w]] += 1
                dq.append(w)

    sys.stdout.write(str(cnt[0] * cnt[1] - (n - 1)) + "\n")


if __name__ == "__main__":
    solve()

---

示例推演

以题面的链 1 - 2 - 3 - 4 为例，从 1 号点开始 BFS：

点	到 1 号点的距离	颜色
1	0	0（黑）
2	1	1（白）
3	2	0（黑）
4	3	1（白）

于是 c0 = 2（点 1、3），c1 = 2（点 2、4），完全二分图共有 2 × 2 = 4 条边，
其中已有的树边是 4 - 1 = 3 条，还能加 4 - 3 = 1 条，正是说明里的 (1, 4)。

再看链 1 - 2 - 3 - 4 - 5：颜色依次是 0、1、0、1、0，所以 c0 = 3（点 1、3、5），
c1 = 2（点 2、4）。完全二分图共有 3 × 2 = 6 条边，树边 5 - 1 = 4 条，
答案是 6 - 4 = 2。逐条看也吻合：黑 {1,3,5} 与白 {2,4} 的 6 个组合里，
(1,2)、(2,3)、(3,4)、(4,5) 已经是树边，能加的正是 (1,4) 与 (2,5)。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
枚举所有加边集合	指数级	O(n)	完全不可行
BFS 染色 + 公式	O(n)	O(n)	推荐，邻接表存储

---

易错点总结

1. 忘记减去原有的 n - 1 条边

c0 * c1 是新图的总边数上限，不是「能加几条」。答案是 c0 * c1 - (n - 1)。

2. 以为可以换一种二分划分来多凑边

树是连通的，二分划分唯一（只差黑白互换），没有「换一种分法」的自由。
只有多个连通块时才需要讨论块内颜色翻转。

3. n = 1 时算成负数

此时 c0 = 1、c1 = 0，c0 * c1 = 0，树边 0 条，答案是 0。
公式本身没问题，但如果把初始计数写成两边都是 1，就会得到 -1。

4. 递归 DFS 爆栈

n = 10^5 的链会让递归深度达到 10^5。用 BFS（或显式栈），
或者在递归版里加上 sys.setrecursionlimit(10**6)。

---

扩展思考

• 如果输入是森林（若干棵树），那么「二分划分」在每棵树内部可以独立翻转，
  为了让 c0 * c1 最大，应该把每棵树的两种颜色中较大的那一类放进同一个集合，
  答案变成「各棵树较大颜色数之和」乘以「较小颜色数之和」再减掉原有的边数。
• 如果允许删边再加边，问题会变成求「在同顶点集上边数最多的二分图」，
  答案就退化成 ⌊n²/4⌋。
• 二分图判定（BFS 染色）是图论里最基础的模板，奇环检测、二分图最大匹配都以它为前提。

---

相关题目

• 小O的树上路径