Submission #990477

---

Source Code Expand

#include <string>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <tuple>

using EdgeList = std::vector<std::vector<int>>;
using Stack = std::vector<std::tuple<int, int>>;
using RemoveSet = std::unordered_set<int>;
using CheckList = std::vector<bool>;

int countInDiameter (EdgeList const & e, Stack & stack, CheckList & checklist, int D, int start) {
  stack.clear();
  stack.emplace_back(start, 0);

  int z = 0;
  while (stack.size() > 0) {
    int v;
    int d;
    std::tie(v, d) = stack.back();
    stack.pop_back();
    checklist[v] = false;
    for (int v2 : e[v]) {
      if (checklist[v2]) {
        stack.emplace_back(v2, d + 1);
      }
    }
    if (d <= D) {
      z += 1;
    }
  }
  return z;
}

int main () {
  std::string line;
  char * p;

  std::getline(std::cin, line);
  p = &line[0];

  int N = std::strtol(p, &p, 10);
  int K = std::strtol(p, &p, 10);

  EdgeList E(N);
  std::vector<std::tuple<int, int>> E2(N - 1);
  for (int i = 0; i < N - 1; ++i) {
    std::getline(std::cin, line);
    p = &line[0];
    int A = std::strtol(p, &p, 10) - 1;
    int B = std::strtol(p, &p, 10) - 1;
    E[A].emplace_back(B);
    E[B].emplace_back(A);
    E2.emplace_back(A, B);
  }

  Stack stack;
  CheckList checklist(N, true);

  int zmax = 0;
  if (K % 2 == 0) {
    for (int i = 0; i < N; ++i) {
      std::fill(checklist.begin(), checklist.end(), true);
      zmax = std::max(zmax, countInDiameter(E, stack, checklist, K / 2, i));
    }
  } else {
    for (int i = 0; i < N - 1; ++i) {
      std::fill(checklist.begin(), checklist.end(), true);
      zmax = std::max(zmax, countInDiameter(E, stack, checklist, (K - 1)/ 2, std::get<0>(E2[i])));
      std::fill(checklist.begin(), checklist.end(), true);
      zmax = std::max(zmax, countInDiameter(E, stack, checklist, (K - 1)/ 2, std::get<1>(E2[i])));
    }
  }

  std::cout << N - zmax << std::endl;
}

Submission Info

Judge Result