本文共 1683 字，大约阅读时间需要 5 分钟。

给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。

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

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

输入格式

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

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

输出格式

输出一个整数m，表示重心的所有的子树中最大的子树的结点数目。

数据范围

1≤n≤1051≤n≤105

输入样例

91 21 71 42 82 54 33 94 6

输出样例：

4

import java.io.*;import java.lang.*;import java.util.*;class Main{        static int n = 0;    static int N = 100010;    static int[] h = new int[2 * N];//邻接表的数组    static int[] e = new int[2 * N], ne = new int[2 * N];//单链表    static int idx = 1;    static int max = N;    static boolean[] f = new boolean[N];//标记当前节点是否被访问过    static void add(int k, int n){        e[idx] = n; ne[idx] = h[k]; h[k] = idx++;    }        static int dfs(int p){        f[p] = true;        int sum = 1, res = 0;        for(int i = h[p]; i != -1; i = ne[i]){            int j = e[i];            if(!f[j]){                int s = dfs(j);//对应j 连通块的结点个数                res = Math.max(res, s);//比较所有子节点连通块的节点数                                sum += s;//计算所有子连通块的节点总和            }        }        res = Math.max(res, n - sum);//比较上面联通块与子连通块的大小        max = Math.min(max, res);        return sum;    }    public static void main(String[] args)throws Exception{        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));        n = Integer.valueOf(buf.readLine());        Arrays.fill(h, -1);        for(int i = 0; i < n - 1; ++i){            String[] info = buf.readLine().split(" ");            int a = Integer.valueOf(info[0]);            int b = Integer.valueOf(info[1]);            add(a, b);//创建无向图，树也是无向图的一种            add(b, a);        }        dfs(1);        System.out.print(max);                    }}