Cod sursa(job #2841558)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 29 ianuarie 2022 21:36:02
Problema Salvare Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("salvare.in");
ofstream fout("salvare.out");

const int kN = 1e3;
vector<int> g[1 + kN];
int n, k, N, deg[1 + kN], dp[1 + kN], q[1 + kN], d[1 + kN], sol[1 + kN];
bitset<1 + kN> mark;

void min_self(int &x, const int &y) {
  if (y < x) {
    x = y;
  }
}

bool check(int m) {
  int st = 0, dr = -1;
  for (int i = 1; i <= n; ++i) {
    deg[i] = g[i].size();
    dp[i] = INF;
    if (deg[i] == 1) {
      dp[i] = m;
      q[++dr] = i;
    }
    mark[i] = false;
  }
  N = 0;
  vector<int> order;
  while (st <= dr) {
    int u = q[st++];
    order.emplace_back(u);
    for (int v : g[u]) {
      min_self(dp[v], dp[u]);
      if (--deg[v] == 1) {
        if (--dp[v] == 0) {
          sol[++N] = v;
          if (k < N) {
            return false;
          }
          dp[v] = m << 1 | 1;
        }
        q[++dr] = v;
      }
    }
  }
  st = 0, dr = -1;
  for (int v = 1; v <= n; ++v) {
    d[v] = INF;
  }
  for (int i = 1; i <= n; ++i) {
    d[sol[i]] = 0;
    q[++dr] = sol[i];
  }
  while (st <= dr) {
    int u = q[st++];
    for (int v : g[u]) {
      if (d[v] > d[u] + 1) {
        d[v] = d[u] + 1;
        q[++dr] = v;
      }
    }
  }
  bool ok = true;
  for (int v = 1; v <= n && ok; ++v) {
    if (d[v] > m) {
      ok = false;
    }
  }
  if (!ok) {
    if (N == k) {
      return false;
    }
    reverse(order.begin(), order.end());
    for (int v : order) {
      if (!mark[v]) {
        sol[++N] = v;
        break;
      }
    }
  }
  return true;
}

void testCase() {
  fin >> n >> k;
  for (int i = 1; i < n; ++i) {
    int u, v;
    fin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  if (n == k) {
    fout << "0\n";
    for (int i = 1; i <= n; ++i) {
      fout << i << ' ';
    }
    fout << '\n';
    return;
  }
  int step = 1;
  while ((step << 1) <= n - 1) {
    step <<= 1;
  }
  int ans = 0;
  while (step >= 1) {
    if (!check(ans | step)) {
      ans |= step;
    }
    step >>= 1;
  }
  ++ans;
  check(ans);
  fout << ans << '\n';
  for (int v = 1; v <= n; ++v) {
    mark[v] = false;
  }
  for (int i = 1; i <= N; ++i) {
    mark[sol[i]] = true;
  }
  for (int i = 1; i <= n && N < k; ++i) {
    if (!mark[i]) {
      sol[++N] = i;
    }
  }
  sort(sol + 1, sol + N + 1);
  for (int i = 1; i <= k; ++i) {
    fout << sol[i] << ' ';
  }
  fout << '\n';
}

int main() {
  int tests = 1;
  for (int tc = 1; tc <= tests; ++tc) {
    testCase();
  }
  fin.close();
  fout.close();
  return 0;
}