题目描述

树的重心

对复杂度的分析一直是弱项, 如果分析不对还请指出我修改~

算法1

(暴力枚举) $O(很高) O(n^n)$

过不了

时间复杂度

算法2

(带记忆的递归) $O(n + e)$

时间复杂度

生成数组 O(n)
删掉某个节点后的子树们的节点数量 O(n)

参考文献

Java 代码

/*
构建邻接表的图 Node, neigh
DFS整个图，每个节点保存以当前节点为根节点的树的节点数量。
再次遍历所有节点, 每个节点都是一个潜在的重心，其最大子树的最小节点数量为 
    1. 总结点数量-当前节点节点数量,
    2. 当前节点分叉的节点树的最大节点树
    1.2.3取max，每次再不同的max中找min min最小的就是重心

*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class AC846 {
  public static Node[] nodes;
  public static boolean[] visited;
  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(reader.readLine());
    nodes = new Node[n + 1];
    visited = new boolean[n + 1];
    for (int i = 1; i <= n; i++){
      nodes[i] = new Node(i);
    }
    while(n -- > 1){
      String[] line = reader.readLine().split(" ");
      int a = Integer.parseInt(line[0]);
      int b = Integer.parseInt(line[1]);
      nodes[a].add(b);
      nodes[b].add(a);
    }
    dfs(1); // 把所有为树根的节点数求出来

    // 这里用不到，但是如果题目要求输出多少个重心的时候就可以在更新minMax的时候更新为1或者++
    int count = 0;
    int minMax = 0x3f3f3f3f;
    for(int i = 1; i < nodes.length; i++){
      int tempMax = 0;
      for(Node nn : nodes[i].neigh){
        if(nn.total > nodes[i].total){ // 如果邻居是父节点
          tempMax = Math.max(nodes.length - 1 - nodes[i].total, tempMax);
        }else{
          tempMax = Math.max(nn.total, tempMax);
        }
      }
      minMax = Math.min(minMax, tempMax);
    }
    System.out.println(minMax);
  }
  public static int dfs(int i){
    int sum = 1;
    visited[i] = true;
    for(Node n : nodes[i].neigh){
      if(!visited[n.val]){
        sum += dfs(n.val);
      }
    }
    nodes[i].total = sum;
    return sum;
  }
  static class Node{
    int val;
    int total;
    List<Node> neigh;
    public Node(int val){
      this.val = val;
      neigh = new ArrayList<>();
    }
    public void add(int t){
      this.neigh.add(nodes[t]);
    }
  }
}