只记得y总讲的思路，不记得具体如何实现的了，自己写的代码又长又乱。。。

import java.io.*;
import java.util.*;

class Main {

    //稀疏图，采用邻接表存储
    static int n;
    static int[] h = new int[100010];
    static int[] e = new int[200010];
    static int[] ne = new int[200010];
    //此点为根节点的子树结点之和
    static int[] v = new int[100010];
    //将这个点删除后，剩余各个连通块中点数的最大值
    static int[] ans = new int[100010];
    //是否已经确定
    static boolean[] flag = new boolean[100010];


    static int idx;
    static int res, maxRegion;

    static {
        Arrays.fill(h,-1);
        Arrays.fill(e,-1);
        Arrays.fill(ne,-1);
    }

    //新建边
    static void link(int a, int b) {
        //插入a顶点
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
        //插入b顶点
        e[idx] = a;
        ne[idx] = h[b];
        h[b] = idx++;
    }

    //计算以x点为根的子树的结点数
    static void dfs(int x) {
        int maxRegion = 0;
        int sum = 0;
        flag[x] = true;
        //遍历所有子树
        for (int t = h[x]; t!= -1; t = ne[t]) {
            if (flag[e[t]]) {
                sum += v[e[t]];
                maxRegion = Math.max(v[e[t]],maxRegion);
            } else {
                dfs(e[t]);
                sum += v[e[t]];
                maxRegion = Math.max(v[e[t]],maxRegion);
            }
        }
        v[x] = sum+1;
        maxRegion = Math.max(maxRegion,n-v[x]);
        ans[x] = maxRegion;
    }

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(isr);
        String[] strs = in.readLine().split(" ");
        n = Integer.parseInt(strs[0]);
        for (int i=0; i<n-1; i++) {
            strs = in.readLine().split(" ");
            int a = Integer.parseInt(strs[0]);
            int b = Integer.parseInt(strs[1]);
            link(a,b);
        }

        //编号是1~n可以把1号点当做根节点，从1开始深搜
        dfs(1);

        int minMax = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) minMax = Math.min(minMax,ans[i]);
        System.out.println(minMax);

        in.close();
        isr.close();


    }
}

作者：java的同学
链接：https://www.acwing.com/activity/content/code/content/854739/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。