C - Shorten Diameter AtCoder Grand Contest 001

問題概略
木の直径をK以下にしたい。削除するべき頂点の数は最小でいくつか

制約
2 <= N <= 2000
1 <= K <= N- 1

解法
木には|S|が偶数の時は一つの中心が、奇数の時は2つの中心あり、最大パスがDの時にそれぞれ全体への距離がD/2以下、(D-1)/2以下となる。
最終的な木の中心を決めてやれば、削除するべき頂点はわかる。具体的には全2点間の距離を求めておき、それが遠いものを数えれば良い。

問題の芯
最終的にある状態を作りたい問題では、最後の状態から考える。

類題
D - IntegerotS

 static int N;
    static int[] A;

    public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        int K = ni();
        initNodes(N);
        for (int i = 0; i < N - 1; i++) {
            addEdge(ni() - 1, ni() - 1);
        }
        int[][] len = setTreeDis(nodes);
        boolean[][] was = new boolean[N][N];
        for (int m = 0; m < N; m++) {
            //木の中心が一つの場合
            int cou = 0;
            for (int i = 0; i < N; i++) {
                if (len[m][i] * 2 > K) cou++;
            }
            chMin(cou);
            //2つの時
            for (Integer m2 : nodes[m]) {
                if (was[m][m2]) continue;
                was[m][m2] = was[m2][m] = true;
                cou = 0;
                for (int i = 0; i < N; i++) {
                    if (len[i][m] * 2 > (K - 1) && len[i][m2] * 2 > (K - 1)) {
                        cou++;
                    }
                }
                chMin(cou);
            }
        }
        System.out.println(minRes);
    }

    public static int[][] setTreeDis(ArrayList<Integer>[] edges) {
        int n = edges.length;
        int[][] dis = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (Integer t : edges[i]) {
                dfsTD(dis, edges, i, i, t, 1);
            }
        }
        return dis;
    }

    public static void dfsTD(int[][] res, ArrayList<Integer>[] edges, int f, int r, int v, int dis) {
        res[f][v] = dis;
        for (Integer t : edges[v]) {
            if (t == r) continue;
            dfsTD(res, edges, f, v, t, dis + 1);
        }
    }

    //連結グラフ
    static ArrayList<Integer>[] nodes;

    static void initNodes(int v) {
        nodes = Stream.generate(ArrayList::new).limit(v).toArray(ArrayList[]::new);
    }

    static void addEdge(int f, int t) {
        nodes[f].add(t);
        nodes[t].add(f);
    }