华为OD- 找城市-2024年OD（D卷）

题目描述

一张地图上有n个城市，城市和城市之间有且只有一条道路相连：要么直接相连，要么通过其它城市中转相连（可中转一次或多次）。城市与城市之间的道路都不会成环。

当切断通往某个城市 i 的所有道路后，地图上将分为多个连通的城市群，设该城市i的聚集度为DPi（Degree of Polymerization），DPi = max（城市群1的城市个数，城市群2的城市个数，…城市群m 的城市个数）。

请找出地图上DP值最小的城市（即找到城市j，使得DPj = min(DP1,DP2 … DPn))

提示：如果有多个城市都满足条件，这些城市都要找出来（可能存在多个解）

提示：DPi的计算，可以理解为已知一棵树，删除某个节点后；生成的多个子树，求解多个子数节点数的问题。

输入描述

每个样例：第一行有一个整数N，表示有N个节点。1 <= N <= 1000。

接下来的N-1行每行有两个整数x，y，表示城市x与城市y连接。1 <= x, y <= N

输出描述

输出城市的编号。如果有多个，按照编号升序输出。

用例

解题思路

问题描述

给定一个 nnn 个节点的树，求出所有可能的「重心节点」。重心节点定义为：移除该节点后，剩余各部分中的最大节点数量最小。

数学逻辑

1. 重心定义：

   • 对于每个节点 iii，移除节点后，将树分成若干个子树。
   • 对每个子树，计算其节点数。
   • 找出所有节点中，移除后子树中最大节点数最小的节点。

2. 递归思想：

   • 使用 DFS 遍历树，计算每个节点的子树大小（包括自己）。
   • 对于每个节点 iii：
     • 遍历其所有相邻节点（子节点）。
     • 递归地计算每个子节点的子树大小。
     • 更新当前节点的最大子树节点数（包括移除当前节点后剩下的子树）。

3. 最终目标：

   • 遍历所有节点，找到移除该节点后最大子树大小最小的节点集合。

 python源码：

from collections import defaultdict

# 深度优先搜索（DFS）计算每个节点的子树大小和最大子树大小
def dfs(city, parent, graph, subtree_sizes, n):
    size = 1  # 初始化当前节点的子树大小
    max_subtree = 0  # 当前节点的最大子树大小

    # 遍历当前节点的所有邻居
    for neighbor in graph[city]:
        if neighbor == parent:  # 跳过父节点，避免回溯
            continue
        # 递归计算子节点的子树大小
        child_size = dfs(neighbor, city, graph, subtree_sizes, n)
        size += child_size  # 累加子节点的大小到当前节点
        max_subtree = max(max_subtree, child_size)  # 更新最大子树大小
    
    # 计算移除当前节点后剩余部分的大小
    max_subtree = max(max_subtree, n - size)
    subtree_sizes[city] = max_subtree  # 保存当前节点的最大子树大小
    return size  # 返回当前节点的子树大小

# 主函数：计算树的重心
def getResult():
    # 输入节点数量
    n = int(input())
    # 用邻接表表示树
    graph = defaultdict(list)

    # 输入树的边
    for _ in range(n - 1):
        x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)
    
    # 初始化子树大小数组
    subtree_sizes = [0] * (n + 1)
    min_dp = n  # 初始化最小的最大子树大小为 n
    result = []  # 存储所有可能的重心节点

    # 遍历所有节点，计算每个节点的最大子树大小
    for i in range(1, n + 1):
        dfs(i, -1, graph, subtree_sizes, n)  # 以 i 为根节点计算子树大小
        if subtree_sizes[i] < min_dp:  # 如果找到更小的最大子树大小
            min_dp = subtree_sizes[i]
            result = [i]  # 更新结果为当前节点
        elif subtree_sizes[i] == min_dp:  # 如果相等，添加到结果列表
            result.append(i)
    
    # 按升序输出所有重心节点
    print(" ".join(map(str, sorted(result))))

# 调用主函数
getResult()

java源码：

import java.util.*;

public class m3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 输入节点数量
        int n = sc.nextInt();
        
        // 初始化图的邻接表表示
        ArrayList<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 输入图的边并建立邻接表
        for (int i = 0; i < n - 1; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph[x].add(y);
            graph[y].add(x);
        }
        
        // 计算并输出重心节点
        System.out.println(findMinDP(n, graph));
    }

    // 查找重心节点的方法
    public static String findMinDP(int n, ArrayList<Integer>[] graph) {
        int minDP = Integer.MAX_VALUE; // 初始化最小的最大子树大小
        ArrayList<Integer> result = new ArrayList<>(); // 存储重心节点的结果列表

        // 遍历所有节点，逐一计算每个节点的最大子树大小
        for (int i = 1; i <= n; i++) {
            int[] maxSubtreeSize = new int[1]; // 存储当前节点的最大子树大小
            boolean[] visited = new boolean[n + 1]; // 标记访问过的节点
            visited[i] = true; // 当前节点被访问
            int largestSubtree = 0; // 当前节点的最大子树大小

            // 遍历当前节点的所有邻居节点
            for (int neighbor : graph[i]) {
                // 通过 DFS 计算子树大小
                int subtreeSize = dfs(neighbor, graph, visited, maxSubtreeSize);
                largestSubtree = Math.max(largestSubtree, subtreeSize); // 更新最大子树大小
            }

            // 判断是否更新最小的最大子树大小
            if (largestSubtree < minDP) {
                minDP = largestSubtree; // 更新最小的最大子树大小
                result.clear(); // 清空之前的结果
                result.add(i); // 添加当前节点为重心
            } else if (largestSubtree == minDP) {
                result.add(i); // 如果相等，则添加当前节点
            }
        }
        
        // 按升序排列重心节点，并以字符串形式返回
        result.sort(Comparator.naturalOrder());
        return String.join(" ", result.stream().map(String::valueOf).toArray(String[]::new));
    }

    // 深度优先搜索（DFS）计算子树大小
    public static int dfs(int node, ArrayList<Integer>[] graph, boolean[] visited, int[] maxSubtreeSize) {
        visited[node] = true; // 标记当前节点为访问过
        int size = 1; // 当前节点的子树大小为 1（自身）
        
        // 遍历所有相邻节点
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) { // 如果邻居节点未被访问
                int subtreeSize = dfs(neighbor, graph, visited, maxSubtreeSize); // 递归计算子树大小
                size += subtreeSize; // 将子树大小累加到当前节点的子树大小
                maxSubtreeSize[0] = Math.max(maxSubtreeSize[0], subtreeSize); // 更新最大子树大小
            }
        }
        
        return size; // 返回当前节点的子树大小
    }
}