解法
よくわからない理論で通ってしまったので後で想定解も書きます。ここでは本番に自分が書いた解法を書きます。
頂点 v が, 木の直径をなす一つの頂点であるとします。
このとき, v は葉になっていないといけないので, v から伸びる辺の数が 1 になるように調整します。
で, このもとで v からの距離が K 以下のものだけを残します。また, 距離が K 以下の頂点のうち, 最も v から離れている頂点 u を選びます。この v, u からの距離がどちらも K 以下である頂点だけを残します。
というのを v について全探索して消す頂点数が最小のものを選びます。
struct edge { int v; ll w; edge() {} edge(int v, ll w) : v(v), w(w) {}; }; vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) { vector<ll> d(n, LLONG_MAX/10); d[s] = 0; priority_queue<pair<ll, int> > que; que.push(make_pair(0ll, s)); while (!que.empty()) { auto p = que.top(); que.pop(); int u = p.second; ll dist = -p.first; if (dist > d[u]) continue; for (edge e : G[u]) { if (d[e.v] > d[u]+e.w) { d[e.v] = d[u] + e.w; que.push(make_pair(-d[e.v], e.v)); } } } return d; } void dfs(int v, int p, vi& vs, const vector<vector<edge> >& G) { vs.push_back(v); for (auto e : G[v]) if (e.v != p) { dfs(e.v, v, vs, G); } } ll dist[2222][2222]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, K; cin >> N >> K; vector<vector<edge> > G(N); for (int i = 0; i < N-1; i++) { int u, v; cin >> u >> v; u--; v--; G[u].emplace_back(v, 1); G[v].emplace_back(u, 1); } for (int i = 0; i < N; i++) { auto d = dijkstra(N, G, i); for (int j = 0; j < N; j++) dist[i][j] = d[j]; } int ans = N; for (int i = 0; i < N; i++) { int leaf = -1, maxi = 0; for (auto e : G[i]) { int ch = e.v; vi vs; dfs(ch, i, vs, G); int sz = vs.size(); int cnt = N-sz-1; vi exist; for (int v : vs) { if (dist[i][v] > K) cnt++; else { exist.push_back(v); if (maxi < dist[i][v]) { maxi = dist[i][v]; leaf = v; } } } for (int v : exist) { if (dist[leaf][v] > K) cnt++; } ans = min(ans, cnt); } } cout << ans << endl; return 0; }