题解 | #小O的叶子#

题目链接

小O的叶子

题目描述

给定一棵 $n$ 个节点的树。你需要删除其中一个节点以及与它相连的所有边。问在所有可能的删除方案中，剩下的森林（由若干连通分量组成）中叶子节点的总数最多是多少？

叶子节点的定义：有且仅有一个节点与之相连的节点（即度数为 1）。

解题思路

这是一个对树的结构进行分析的题目。我们可以遍历删除每一个节点，计算删除后剩下图中的叶子节点数，然后取最大值。关键在于如何高效地计算每次删除后的叶子数。

1. 高效计算策略：分析变化量

一个直接但低效的方法是，对每个待删除的节点 u，都重新构建图并统计叶子数，这将导致 $\mathcal{O}(N^2)$ 的复杂度。

更高效的方法是，我们先计算出原始树的总叶子数 initial_leaves，然后对于每一次删除操作，我们只关注叶子数量的变化量。

2. 分析删除节点 u 带来的影响

当一个节点 u 被删除时，只有 u 本身和与 u 直接相连的邻居节点的“叶子状态”可能会发生改变。所有其他节点的度数不变，因此它们的叶子状态也不变。

我们可以分情况讨论删除 u 带来的叶子数增减：

失去的叶子:
1. u 本身: 如果被删除的节点 u 在原树中就是一个叶子（度数为 1），那么删除它会使总叶子数减少 1。
2. u 的叶子邻居: 如果 u 的某个邻居 v 在原树中是叶子（度数为 1），那么 u 是 v 唯一的邻居。当 u 被删除后，v 会变成一个度数为 0 的孤立点，不再是叶子。因此，每有一个这样的叶子邻居，总叶子数就会减少 1。
新增的叶子:
1. u 的非叶子邻居: 考虑 u 的一个邻居 v，它在原树中不是叶子（度数 > 1）。当 u 被删除后，v 的度数会减 1。如果 v 的新度数恰好变为 1，那么它就成为了一个新的叶子节点。这当且仅当 v 在原树中的度数正好为 2 时才会发生。因此，每有一个度数为 2 的邻居，总叶子数就会增加 1。

3. 算法流程

预处理:
- 读入所有边，建立邻接表。
- 遍历所有节点，计算并存储每个节点的度数 degree[i]。
计算初始叶子数:
- 遍历所有节点，统计度数为 1 的节点总数，记为 initial_leaves。
遍历所有删除方案:
- 初始化一个变量 max_leaves = 0 用于记录最大值。
- 从 i = 1 到 n 循环，将 i 作为当前要删除的节点： a. 计算叶子数的变化量 change = 0。 b. 如果 degree[i] == 1 (要删除的节点是叶子)，change 减 1。 c. 遍历节点 i 的所有邻居 j： - 如果 degree[j] == 1 (邻居是叶子)，change 减 1。 - 如果 degree[j] == 2 (邻居可能变叶子)，change 加 1。 d. 计算删除节点 i 后的总叶子数：current_leaves = initial_leaves + change。 e. 更新最大值：max_leaves = max(max_leaves, current_leaves)。
输出结果: max_leaves 即为最终答案。

这个算法的总时间复杂度为 $\mathcal{O}(N)$ ，因为预处理和主循环都只涉及对节点和边的线性扫描。

代码

cpp
java
python

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if (n == 2) {
        cout << 1 << endl;
        return 0;
    }

    vector<vector<int>> adj(n + 1);
    vector<int> degree(n + 1, 0);

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }

    int initial_leaves = 0;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] == 1) {
            initial_leaves++;
        }
    }

    int max_leaves = 0;
    for (int i = 1; i <= n; ++i) {
        int change = 0;
        if (degree[i] == 1) {
            change = -1;
        }

        for (int neighbor : adj[i]) {
            if (degree[neighbor] == 1) {
                change--;
            } else if (degree[neighbor] == 2) {
                change++;
            }
        }
        max_leaves = max(max_leaves, initial_leaves + change);
    }

    cout << max_leaves << endl;

    return 0;
}

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

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

        if (n == 2) {
            System.out.println(1);
            return;
        }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        int[] degree = new int[n + 1];

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

        int initialLeaves = 0;
        for (int i = 1; i <= n; i++) {
            if (degree[i] == 1) {
                initialLeaves++;
            }
        }

        int maxLeaves = 0;
        for (int i = 1; i <= n; i++) {
            int change = 0;
            if (degree[i] == 1) {
                change = -1;
            }

            for (int neighbor : adj.get(i)) {
                if (degree[neighbor] == 1) {
                    change--;
                } else if (degree[neighbor] == 2) {
                    change++;
                }
            }
            maxLeaves = Math.max(maxLeaves, initialLeaves + change);
        }

        System.out.println(maxLeaves);
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
    except (IOError, ValueError):
        return

    if n == 2:
        print(1)
        return

    adj = [[] for _ in range(n + 1)]
    degree = [0] * (n + 1)

    for _ in range(n - 1):
        u, v = map(int, sys.stdin.readline().split())
        adj[u].append(v)
        adj[v].append(u)
        degree[u] += 1
        degree[v] += 1

    initial_leaves = 0
    for i in range(1, n + 1):
        if degree[i] == 1:
            initial_leaves += 1

    max_leaves = 0
    for i in range(1, n + 1):
        change = 0
        if degree[i] == 1:
            change = -1
        
        for neighbor in adj[i]:
            if degree[neighbor] == 1:
                change -= 1
            elif degree[neighbor] == 2:
                change += 1
        
        max_leaves = max(max_leaves, initial_leaves + change)

    print(max_leaves)

solve()

算法及复杂度

算法: 图论、枚举
时间复杂度:
- 构建邻接表和度数数组： $\mathcal{O}(N)$ ，因为我们遍历了 $N-1$ 条边。
- 计算初始叶子节点数： $\mathcal{O}(N)$ 。
- 主循环遍历 $N$ 个节点作为删除候选。在循环内部，我们遍历该节点的邻居。由于树中所有节点的度数之和为 $2(N-1)$ ，因此整个双层循环的总操作次数正比于边数，为 $\mathcal{O}(N)$ 。
- 总时间复杂度为 $\mathcal{O}(N)$ 。
空间复杂度:
- 邻接表需要 $\mathcal{O}(N)$ 的空间来存储 $N-1$ 条边。
- 度数数组需要 $\mathcal{O}(N)$ 的空间。
- 总空间复杂度为 $\mathcal{O}(N)$ 。