题解 | #小O的树上加边#

题目链接

小O的树上加边

题目描述

给定一棵由 $n$ 个点组成的树。我们知道任何树都是一个二分图。

问题是，我们最多可以向这棵树中添加多少条边，使得新生成的图仍然是一个二分图。

解题思路

这是一个关于二分图性质的典型问题。核心思想是利用树的结构特点来解决。

1. 树与二分图

一个重要的图论性质是：任何树都是二分图。这是因为树中不存在任何环路，所以自然也不存在奇数长度的环路，而一个图是二分图的充要条件就是它不包含奇数长度的环路。

2. 二分图的划分

既然树是二分图，我们就可以将其所有节点划分成两个不相交的集合 $U$ 和 $V$ ，使得树中所有的边都连接着一个 $U$ 中的点和一个 $V$ 中的点。

为了找到这两个集合，我们可以使用 图的二分染色 算法。具体步骤如下：

选择一个任意的起始节点（例如，节点1），将其染成颜色1。
使用广度优先搜索（BFS）或深度优先搜索（DFS）遍历整棵树。
在遍历过程中，当我们从一个颜色为 $c$ 的节点 $u$ 访问其未染色的邻居节点 $v$ 时，我们将 $v$ 染成与 $u$ 不同的颜色（例如，颜色2）。
遍历结束后，所有被染成颜色1的节点可以构成集合 $U$ ，所有被染成颜色2的节点构成集合 $V$ 。

3. 计算最大可添加边数

在一个二分图中，为了保持其二分图的性质，我们新添加的任何边都必须连接一个 $U$ 中的点和一个 $V$ 中的点。在两个集合内部（例如，连接 $U$ 中的两个点）添加边会产生一个奇数环，从而破坏二分图的性质。

因此，要使图中的边数最多，我们应该把它变成一个 完全二分图。在一个划分大小分别为 $|U|$ 和 $|V|$ 的完全二分图中，总边数为 $|U| \cdot |V|$ 。

设通过染色，我们得到两个集合的大小分别为 $n_1$ 和 $n_2$ 。那么，这个图最多可以容纳 $n_1 \cdot n_2$ 条边。

原始的树已经包含了 $n-1$ 条边。所以，我们最多还可以添加的边数就是： $n_1 \cdot n_2 - (n - 1)$

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

vector<int> adj[100005];
int color[100005];
long long counts[3] = {0, 0, 0};

void dfs(int u, int c, int p) {
    color[u] = c;
    counts[c]++;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, 3 - c, u);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 1, 0);

    long long result = counts[1] * counts[2] - (n - 1);
    cout << result << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer>[] adj;
    static int[] color;
    static long[] counts;

    public static void dfs(int u, int c, int p) {
        color[u] = c;
        counts[c]++;
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, 3 - c, u);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj[u].add(v);
            adj[v].add(u);
        }

        color = new int[n + 1];
        counts = new long[3]; // counts[1] and counts[2]

        dfs(1, 1, 0);

        long result = counts[1] * counts[2] - (n - 1);
        System.out.println(result);
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(200005)

def dfs(u, c, p, adj, color, counts):
    color[u] = c
    counts[c] += 1
    for v in adj[u]:
        if v != p:
            dfs(v, 3 - c, u, adj, color, counts)

def main():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        
        adj = [[] for _ in range(n + 1)]
        for _ in range(n - 1):
            u, v = map(int, sys.stdin.readline().split())
            adj[u].append(v)
            adj[v].append(u)
            
        color = [0] * (n + 1)
        # counts[1] 和 counts[2]
        counts = [0, 0, 0]
        
        dfs(1, 1, 0, adj, color, counts)
        
        result = counts[1] * counts[2] - (n - 1)
        print(result)

    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：图的二分染色（通过 DFS 或 BFS 实现）。
时间复杂度：我们需要遍历整棵树一次来完成染色。图的遍历算法（DFS/BFS）的时间复杂度是 $\mathcal{O}(V+E)$ ，其中 $V$ 是节点数， $E$ 是边数。对于一棵树， $V=n$ 且 $E=n-1$ ，所以时间复杂度是 $\mathcal{O}(n)$ 。
空间复杂度：我们需要一个邻接表来存储树的结构，空间为 $\mathcal{O}(n)$ 。此外，还需要一个数组来记录每个节点的颜色，以及递归栈的空间（对于DFS），这些也都是 $\mathcal{O}(n)$ 。因此，总空间复杂度为 $\mathcal{O}(n)$ 。