题目描述

给定一个 \(N\) 个点的树，你要从中选出一个大小为 \(k\) 的子树出来，求这个子树的最小直径。

思路

由于此题允许 \(O(N^2)\) 的时间复杂度，所以考虑枚举子树的中心。

接着以该中心为根向下搜出深度为 \(i\) 的结点数 \(cnt_i\)，接着枚举直径长度除 \(2\)。由于这里直径可能长度为偶数，则此时中点在一条边上。所以我们把每条边也看作一个点（但不统计在 \(cnt\) 中）。找到第一个 \(\sum \limits_{i=0}^x cnt_i \ge k\) 的 \(x\)，并统计答案即可。

空间复杂度 \(O(N)\)，时间复杂度 \(O(N^2)\)。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 2001;

int n, k, dep[MAXN], cnt[MAXN], ans;
vector<int> e[MAXN];

void dfs(int u, int fa) {
  dep[u] = dep[fa] + 1;
  cnt[dep[u]] += (u <= n);
  for(int v : e[u]) {
    if(v != fa) {
      dfs(v, u);
    }
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for(int i = 1, u, v; i < n; ++i) {
    cin >> u >> v;
    e[u].push_back(n + i);
    e[n + i].push_back(v);
    e[v].push_back(n + i);
    e[n + i].push_back(u);
  }
  ans = 2 * n;
  for(int i = 1; i < 2 * n; ++i) {
    for(int j = 1; j <= 2 * n; ++j) {
      dep[j] = cnt[j] = 0;
    }
    dfs(i, 0);
    int res = 0;
    for(int j = 1; j <= 2 * n; ++j) {
      res += cnt[j];
      if(res >= k) {
        ans = min(ans, j);
        break;
      }
    }
  }
  cout << ans;
  return 0;
}