题目描述

树的重心

样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

算法

java 代码

import java.util.*;
public class Main {
    // 存储每个节点的子节点数（包括自己）
    private static Map<Integer, Integer> map = new HashMap<>();
    // 存储每个节点的邻接节点
    private static List<List<Integer>> tree = new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        // 是否被访问过
        boolean[] visited = new boolean[n+1];
        for (int i = 0; i <= n; i++) {
            tree.add(new ArrayList<>());
        }
        while (n-- > 1) {
            int a = in.nextInt();
            int b = in.nextInt();
            tree.get(a).add(b);
            tree.get(b).add(a);
        }

        dfs(1, visited);

        int minMax = tree.size();
        for(int i = 1; i < tree.size(); i++){
            int tempMax = 0;
            for(Integer nn : tree.get(i)){
                if(map.get(nn) > map.get(i)){ // 如果邻居是父节点
                    tempMax = Math.max(tree.size() - 1 - map.get(i), tempMax);
                } else {
                    tempMax = Math.max(map.get(nn), tempMax);
                }
            }
            minMax = Math.min(minMax, tempMax);
        }
        System.out.println(minMax);
    }

    private static int dfs(int n, boolean[] visited) {
        int sum = 1;
        visited[n] = true;
        List<Integer> list = tree.get(n);
        for (int i = 0; i < list.size(); i++) {
            if (!visited[list.get(i)]) {
                sum += dfs(list.get(i), visited);
            }
        }
        map.put(n, sum);
        return sum;
    }
}