题目描述
给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式
第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围
1≤n≤10的五次方

输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例
4

import java.util.*;
public class Main{
    static int N=100010;
    static int M=2*N;
    static int ans=N;
    static boolean[] st=new boolean[N];
    static int n;
    static int[] h=new int[N];
    static int[] e=new int[M];//一个节点要存两条边
    static int[] ne=new int[M];
    static int idx;
    static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    static int dfs(int u){
        st[u]=true;
        int sum=1;
        int res=0;     
        for(int i=h[u];i!=-1;i=ne[i]){
            int j=e[i];
            if(!st[j]){
                int s=dfs(j);//u节点的单棵子树节点数,这一步，返回的值为用于求以当前节点的个子树的节点数量
                //res表示删除u节点后子树的联通数最大数
                res=Math.max(res,s);//记录最大联通子图的节点数
                sum+=s;//以j为根的树的节点数
            }
        }
        //n-sum表示删除u后另外一块的最大值
        res=Math.max(res,n-sum);//选择u节点为重心，最大的连通子图节点数
        ans=Math.min(ans,res);//在所有被假设的重心中，最小的最大的连通子图节点数
        return sum;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        Arrays.fill(h,-1);
        for(int i=0;i<n-1;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            add(a,b);
            add(b,a);
        }
        dfs(1);//可以任意选定一个节点开始u<=n
        System.out.println(ans);
    }
}