問題概要

$N$ 頂点のツリーが与えられる。
ツリーの頂点をいくつか削除することで、ツリーの直径が $K$ となるようにしたい。ただし残るグラフが連結でなければならない。

このようなことを実現するために削除する頂点数の最小値を求めよ。

制約

$2 \le N \le 2000$
$1 \le K \le N - 1$

考えたこと: ツリー DP だけで突っ込むと詰まる

最初は「なんじゃこりゃー」となった。そしてこういう問題は確かに相場はツリー DP と決まっていて、しかもツリー DP にありがちな問題として「根を 1 つ固定してしまってよい」というのが、ありがちな典型思考なのだけど、、、、、

この問題ではその方向性で考えると、迷路に迷い混んでしまう。。。

根を固定したとき、いくつかの部分木に分かれて、それぞれについて直径を $i$ 以下となるようにして...その結果をマージして、、、というのがツリー DP 的な思考過程だと思う。でも、

各部分木について直径が $i$ 以下となるようにしたときの最適解の形がわからないので
その結果をどうマージすればいいのかがよくわからない

という感じで詰まってしまう。

ツリーの中心のことを思い出す

ここでちょっと方針転換をしてみた。ツリーというのは

直径
中心

というのがある。直径が偶数の場合はそのど真ん中にある点が中心である。直径が $2d$ であるとき、中心から各頂点への距離は $d$ 以下になっている。

直径が奇数の場合も、中心をなす辺が存在する感じ。直径が $2d+1$ であるとき、中心辺の両端点を考えて、その各端点を根とする部分木の各頂点への距離は $d$ 以下になっている。

最適解の形に着目する

これを踏まえて、最適解がどうなっているかはわからないけれど、最適解の中心をなる点 or 辺は必ずどこかにあることがわかる。そして、その点 or 辺からの距離が $K/2$ より大きくなっているところは切り落とされていることになる。よって、最適解の中心となっている点 or 辺がもしわかれば、そこから Greedy に距離 $K/2$ より大きいところを切り落とせば良い。

逆に言えば、最適解の中心となる点 or 辺を $N$ 通り or $N-1$ 通りすべて試してそれぞれについての最適解を求めていけば、その中に真の最適解が含まれていることになる。

まとめると、この問題は以下のようにして解くことができる:

$K$ が偶数のときは、 $N$ 通りの各頂点 $v$ について、「 $v$ から距離が $K/2$ より大きい点の個数」を求めて、その最小値をとる
$K$ が奇数のときは、 $N-1$ 通りの各辺 $(u, v)$ について、「 $u$ と $v$ をそれぞれ根とする部分木においてそれぞれ根からの距離が $K/2$ より大きい点の個数の和」を求めて、その最小値をとる

#include <iostream>
#include <vector>
using namespace std;

int N, K;
vector<vector<int> > tree;

// 頂点 v を根として、p のある側は切り落としてできる部分木について
// v から各頂点への距離を depth に格納する
// (特に p = -1 のときは、ツリー全体について v を根とすることを表す)
void rec(int v, int p, int curdepth, vector<int> &depth) {
    depth[v] = curdepth;
    for (auto nv : tree[v]) {
        if (nv == p) continue;
        rec(nv, v, curdepth + 1, depth);
    }
}

int main() {
    cin >> N >> K;
    tree.assign(N, vector<int>());
    for (int i = 0; i < N-1; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        tree[a].push_back(b); tree[b].push_back(a);
    }
    int res = N; // INF の気持ち
    vector<int> depth(N);
    if (K % 2 == 0) {
        for (int v = 0; v < N; ++v) {
            rec(v, -1, 0, depth);
            int num = 0;
            for (int i = 0; i < N; ++i) if (depth[i] > K/2) ++num;
            res = min(res, num);
        }
    }
    else {
        for (int u = 0; u < N; ++u) {
            for (auto v : tree[u]) {
                depth[v] = depth[v] = 0;
                rec(u, v, 0, depth); rec(v, u, 0, depth);
                int num = 0;
                for (int i = 0; i < N; ++i) if (depth[i] > K/2) ++num;
                res = min(res, num);
            }
        }
    }
    cout << res << endl;
}