当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

定理:确定分块大小后,至多只有一种划分方案。

暴力 DP

DFS 自底向上计算,用 dp_u 表示到 u 为止,未被分块的节点个数。

每次需要重新枚举块的大小,时间复杂度为 O(n \cdot \sigma(n)) ,会获得 TLE 的好成绩。

巧妙的优化

有个显然的事情就是每个点只能属于一个联通块。

也就是说,前面我们统计的那个 dp_u ,在做到 u 这个点时,要么把自己和子树未被分配的点分到同一个块内,要么就留着自己等着之后配。也就是说,每个联通块的最高点(深度最浅点)一定满足其子树大小是当前块大小 size 的倍数。

可以证明如果以 size 为大小分块有一种划分方案,那么至少存在 n / size 个点的子树大小是 size 的倍数,反之亦然。

我们可以直接统计下每个点的子树大小放在桶里,然后枚举下分块大小去扫描。复杂度显然低于调和级数的复杂度,故上届为 O(n \log n) ,可以通过此题。

代码

// =================================
//   author: memset0
//   date: 2019.07.14 08:18:13
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define rep(i, l, r) for (int i = (l), i##ed = (r); i <= i##ed; ++i)
#define for_each(i, a) for (size_t i = 0, i##ed = a.size(); i < i##ed; ++i)
namespace ringo {

template <class T> inline void read(T &x) {
  x = 0; char c = getchar(); bool f = 0;
  while (!isdigit(c)) f ^= c == '-', c = getchar();
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  if (f) x = -x;
}
template <class T> inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
template <class T> inline void print(T a, int l, int r, std::string s = "") {
  if (s != "") std::cout << s << ": ";
  for (int i = l; i <= r; i++) print(a[i], " \n"[i == r]);
}

const int N = 1e6 + 10;
int n, ans, siz[N], cnt[N];
std::vector<int> G[N];

void dfs(int u, int father) {
  siz[u] = 1;
  for_each(i, G[u]) {
    int v = G[u][i];
    if (v != father) {
      dfs(v, u);
      siz[u] += siz[v];
    }
  }
  cnt[siz[u]]++;
}

inline bool check(int x) {
  int res = 0;
  for (int i = x; i <= n; i += x)
    res += cnt[i];
  return res == n / x;
}

void main() {
  read(n);
  for (int i = 1, u, v; i < n; i++) {
    read(u), read(v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs(1, 0);
  for (int i = 1; i * i <= n; i++)
    if (n % i == 0) {
      ans += check(i);
      if (i * i != n) ans += check(n / i);
    }
  print(ans, '\n');
}

} signed main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
#endif
  return ringo::main(), 0;
}

参考资料

巧妙的思路 调和级数 找性质 Favorite

NowCoder880D 301045 / 雷的打字机
上一篇 «
NOI 模拟赛 20190711A 刀剑传奇
» 下一篇