Luogu3942 将军令

考虑一个贪心策略。每次找到未被覆盖的最深的点,将其第 $k$ 个祖先进行操作。因为当前找到了最深的点,所以以 $k$ 代祖先为根的子树内的点都会被覆盖,而越往上显然会对越多的点造成影响,所以是对的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int MAXN = 1e5;

int n, k, edge, tail;
int fst[MAXN | 1], dep[MAXN | 1], father[MAXN | 1], stack[MAXN | 1];
bool vis[MAXN | 1];
std::pair < int, int > dot[MAXN | 1];

struct Edge {
  int to, nxt;
  Edge() : to(0), nxt(0) {}
  Edge(int a, int b) : to(b), nxt(fst[a]) {}
} e[MAXN << 1 | 1];

inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}

inline void addEdge(int a, int b) {
  e[++edge] = Edge(a, b);
  fst[a] = edge;
}

void dfs(int x, int fa) {
  dep[x] = dep[fa] + 1;
  stack[++tail] = x;
  father[x] = stack[std::max(1, tail - k)];
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (to == fa) continue;
    dfs(to, x);
  }
  --tail;
}

void bfs(int x) {
  std::queue < std::pair < int, int > > q;
  bool book[MAXN | 1];
  memset(book, 0, sizeof(book));
  q.push(std::make_pair(x, 0));
  book[x] = 1;
  do {
    std::pair < int, int > from = q.front();
    q.pop();
    vis[from.first] = 1;
    if (from.second == k) continue;std
    for (int k = fst[from.first]; k; k = e[k].nxt) {
      int to = e[k].to;
      if (book[to]) continue;
      q.push(std::make_pair(to, from.second + 1));
      book[to] = 1;
    }
  } while (!q.empty());
}

int main() {
  n = read();
  k = read();
  for (int i = 1, a, b; i < n; ++i) {
    a = read();
    b = read();
    addEdge(a, b);
    addEdge(b, a);
  }
  dfs(1, 0);  
  for (int i = 1; i <= n; ++i) dot[i].first = dep[i], dot[i].second = i;
  std::sort(dot + 1, dot + 1 + n);
  int ans = 0;
  for (int i = n; i >= 1; --i) {
    if (vis[dot[i].second]) continue;
    bfs(father[dot[i].second]);
    ++ans;
  }
  printf("%d\n", ans);
  return 0;
}
最后修改:2019 年 08 月 02 日 03 : 26 PM

发表评论