BZOJ4401 块的计数

传送门

分析

结论题。假设分成的每块大小为 \(k\)，则分成了 \(\frac{n}{k}\) 块，也就是 \(k|n\) ，有 \(\frac{n}{k}\) 个节点可以作为每块的根节点，显然，这些节点中每个节点的子树大小一定是 \(k\) 的倍数。

于是，我们可以先 \(dfs\) 一遍求出每个节点子树大小，然后枚举 \(k\) ，统计 \(sz\) 为 \(k\) 的倍数的节点数量，记为 \(num\) ，再判断 \(num\) 是否等于 \(\frac{n}{k}\) 即可。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define il inline
#define re register
#define maxn 1000005
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x) {
    T f = 1; x = 0; char c;
    for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x *= f;
}

struct edge {
    int to, nxt;
} e[maxn<<1];

int n, cnt, ans;
int sz[maxn], head[maxn<<1], ton[maxn];

void insert(int u, int v) {
    e[++cnt].to = v, e[cnt].nxt = head[u], head[u] = cnt;
    e[++cnt].to = u, e[cnt].nxt = head[v], head[v] = cnt;
}

void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v != fa) {
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
}

int main() {
    int u, v;
    read(n);
    for (int i = 1; i < n; ++i) {
        read(u), read(v);
        insert(u, v);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i) ton[sz[i]]++;
    for (int k = 1; k <= n; ++k) {
        int num = 0;
        if (n % k == 0) {
            for (int i = k; i <= n; i += k) num += ton[i];
            if (num == n / k) ans++;
        }
    }
    printf("%d", ans);
    return 0;
}

BZOJ4401 块的计数

原文：https://www.cnblogs.com/hlw1/p/11436825.html