JAVA题解：

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

public class Main {
    static int n;
    static List<List<Integer>> adj;
    static int[] depth;
    static List<List<Integer>> children;
    static int maxDepth = 0;

    static void dfs(int u, int p) {
        for (int v : adj.get(u)) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            maxDepth = Math.max(maxDepth, depth[v]);
            children.get(u).add(v);
            dfs(v, u);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < n-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        depth = new int[n+1];
        children = new ArrayList<>();
        for (int i = 0; i <= n; i++) children.add(new ArrayList<>());

        dfs(1, 0);

        int answer = 0;
        for (int h = 0; h <= maxDepth; h++) {
            List<List<Integer>> byDepth = new ArrayList<>();
            for (int i = 0; i <= maxDepth; i++) byDepth.add(new ArrayList<>());
            for (int v = 1; v <= n; v++) {
                byDepth.get(depth[v]).add(v);
            }

            int[] best = new int[n+1];
            Arrays.fill(best, Integer.MIN_VALUE / 2);
            for (int d = maxDepth; d >= 0; d--) {
                for (int v : byDepth.get(d)) {
                    if (depth[v] > h) {
                        best[v] = Integer.MIN_VALUE / 2;
                    } else if (depth[v] == h) {
                        best[v] = 1;
                    } else {
                        int sum = 0;
                        for (int u : children.get(v)) {
                            if (best[u] > 0) sum += best[u];
                        }
                        best[v] = (sum > 0 ? sum + 1 : Integer.MIN_VALUE / 2);
                    }
                }
            }
            answer = Math.max(answer, best[1]);
        }

        System.out.println(n - answer);
    }
}