AcWing 846. 树的重心

【题目描述】

AcWing 846. 树的重心

【思路】

import java.util.Scanner;
import java.lang.Math;
import java.util.Arrays;
public class Main{
    static int N = 100010, M = 2 * N;
    static int n, idx;
    static int h[] = new int[N];
    static int e[] = new int[M];
    static int ne[] = new int[M];
    static boolean st[] = new boolean[N];
    static int ans = Integer.MAX_VALUE;

    public static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    //深度优先遍历图 u是当前节点，每个节点只被遍历一次，需要用到st标记数组
    public static int dfs(int u){
        st[u] = true; //标记一下，已经访问过了

        int sum = 1, res = 0;
        //u的所有出边
        for(int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];
            if(!st[j])
            {
                //获得以j为根节点的子树的点数
                int s = dfs(j);
                //根节点是j的子树是根节点是u的树的一颗子树
                res = Math.max(res, s);//断开之后的每一个数
                sum += s;//u为根的连通块数 
            }
        }
        res = Math.max(res, n  - sum);
        ans = Math.min(ans, res);
        return sum;
    }
    public static void main(String args[]){
        Scanner reader =new Scanner(System.in);
        n = reader.nextInt();

        //初始化为-1
        Arrays.fill(h, - 1);
        for(int i = 0; i < n - 1; i ++){
            int a = reader.nextInt(), b = reader.nextInt();
            add(a, b);
            add(b, a);
        }
        //初始化数组
        dfs(1);
        System.out.println(ans);
    }
}