H.cc

#include <iostream>
#include <vector>
#define MAXN 1001

using namespace std;

vector<int> adj[MAXN];
bool visit[MAXN];

vector<int> paths, cycles;

inline int single_path(int d, int n) {
  int den = 2 * d + 1, x = (n - 1) / den;
  return x + (n - 1 - x * den > d);
}

int use_root(int dist) {
  int ans = 1, den = 2 * dist + 1;
  for (int x : cycles)
    ans += (x + den - 1) / den - 1;
  for (int x : paths)
    ans += single_path(dist, x);
  return ans;
}

int fix_path(int dist, int cid, int pos) {
  int ans = 1;
  for (int i = 0; i < (int)paths.size(); ++i) {
    if (i == cid)
      ans += single_path(dist, paths[i] - pos);
    else
      ans += single_path(dist, paths[i] + pos);
  }
  return ans;
}

int max_cycle = 0;
int max_path_id = 0;
int solve(int dist) {
  int ans = use_root(dist);
  if (max_cycle < dist and paths.size()) {
    for (int i = 1; i <= min(dist - max_cycle, paths[max_path_id]-1); ++i)
      ans = min(ans, fix_path(dist, max_path_id, i));
  }
  return ans;
}

int root;
void dfs(int u, int d = 1, int p = 0) {
  visit[u] = true;
  bool leaf = true;
  for (int v : adj[u])
    if (v != p) {
      leaf = false;
      if (v == root)
        cycles.push_back(d);
      else if (not visit[v])
        dfs(v, d + 1, u);
    }
  if (leaf)
    paths.push_back(d);
}

int main() {
  ios::sync_with_stdio(0);
  int n, m, k;
  cin >> n >> m >> k;
  int u, v;
  while (m--) {
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  root = 1;
  for (u = 1; u <= n; ++u) {
    if (adj[u].size() == 1)
      root = u;
    else if (adj[u].size() > 2) {
      root = u;
      break;
    }
  }
  //cerr << "root: " << root << endl;
  dfs(root);
  for (int x : cycles)
    max_cycle = max(max_cycle, x);
  max_cycle /= 2;
  for (int i = 1; i < (int)paths.size(); ++i)
    if (paths[max_path_id] < paths[i])
      max_path_id = i;

  int lo = -1, hi = n, mid;
  while (hi - lo > 1) {
    mid = (hi + lo) >> 1;
    //cerr <<  mid << ' ' << solve(mid) << endl;
    if (solve(mid) > k)
      lo = mid;
    else
      hi = mid;
  }
  cout << hi << endl;
  return 0;
}