题解：吊灯染色方案

算法思路

本题需要求解树划分问题：将树划分为若干个连通块，每个连通块大小相同且颜色相同。

核心观察

对于合法的染色方案，存在以下关键性质：

1. 必要条件：每种颜色的灯泡个数 $k$ 必须是 $n$ 的约数
2. 充分条件：存在至少 $n/k$ 个节点，其子树大小是 $k$ 的倍数

数学证明

考虑一个合法的染色方案：

• 整个树被划分为若干个同色连通块，每个大小为 $k$
• 以颜色为节点，不同颜色块之间的父子关系构成有向无环图
• 通过拓扑排序可以证明：一定存在某个同色连通块，其中每个节点都不是其他异色节点的父节点
• 这样的连通块对应一个子树大小为 $k$ 的倍数的节点

算法步骤

对于每种状态（共10种）：

1. 构建树结构：根据输入或调整规则确定父子关系
2. 计算子树大小：从叶子到根进行DFS，计算每个节点的子树大小
3. 统计频数：记录每个子树大小值出现的次数
4. 检查约数：对于每个 $k$（$k \mid n$），检查是否存在至少 $n/k$ 个节点的子树大小是 $k$ 的倍数

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e6;
typedef int arr[MAXN];
arr fa, num, sz;
int N, T;

inline int rd() {
    int x = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

int main() {
    N = rd();
    
    for (T = 1; T <= 10; ++T) {
        // 构建当前状态的树
        for (int i = 2; i <= N; ++i) {
            if (T == 1) {
                fa[i] = rd();
            } else {
                fa[i] = (fa[i] + 19940105) % (i - 1) + 1;
            }
        }
        
        // 初始化
        for (int i = 1; i <= N; ++i) {
            sz[i] = 1;
            num[i] = 0;
        }
        
        // 计算子树大小（自底向上）
        for (int i = N; i > 1; --i) {
            sz[fa[i]] += sz[i];
        }
        
        // 统计各子树大小的出现次数
        for (int i = 1; i <= N; ++i) {
            ++num[sz[i]];
        }
        
        // 输出当前状态
        printf("Case #%d:\n", T);
        printf("1\n");  // k=1 总是可行
        
        // 检查每个可能的 k 值
        for (int k = 2; k <= N; ++k) {
            if (N % k != 0) continue;
            
            int count = 0;
            // 统计子树大小是 k 的倍数的节点数
            for (int j = 1; k * j <= N; ++j) {
                count += num[k * j];
            }
            
            // 检查是否满足条件
            if (count * k >= N) {
                printf("%d\n", k);
            }
        }
    }
    
    return 0;
}

关键点分析

1. 树结构调整

• 第1次使用原始输入
• 后续9次使用公式：$fa[x] = (fa[x] + 19940105) \bmod (x-1) + 1$

2. 子树大小计算

for (int i = N; i > 1; --i) {
    sz[fa[i]] += sz[i];
}

通过自底向上的遍历，高效计算每个节点的子树大小。

3. 可行性检查

对于每个候选 $k$：

• 计算子树大小为 $k, 2k, 3k, \ldots$ 的节点总数
• 如果总数 $\times k \geq n$，则 $k$ 是可行解

复杂度分析

• 时间复杂度：$O(10 \times (n + d(n) \times \frac{n}{k}))$，其中 $d(n)$ 是 $n$ 的约数个数
• 空间复杂度：$O(n)$

对于 $n \leq 1.2 \times 10^6$ 的数据规模，该算法能够高效运行。

正确性保证

算法基于严格的组合数学证明：

• 每个合法划分对应至少 $n/k$ 个"关键节点"
• 通过统计子树大小分布，可以准确判断每个 $k$ 的可行性
• 输出保证按升序排列，且包含所有可行解