九月落叶题解

问题分析

我们有一棵 $N$ 个节点的有根树，根节点为 $0$。落叶过程持续 $K$ 天，每天可以删除多个当前是叶子的节点。$M$ 位志愿者各自记录了落叶顺序，但每天内的删除顺序可以任意排列。

目标：根据志愿者的记录，求出最大可能的落叶天数 $K$。

关键洞察

1. 叶子删除规则：一个节点只有在所有子节点都被删除后才会变成叶子
2. 记录特性：志愿者记录中，同一天删除的节点顺序可以任意排列
3. 最大天数策略：为了最大化 $K$，我们希望在满足所有约束的前提下，尽可能多地分段

算法核心思想

维护的关键变量

• ch[u]：节点 $u$ 的当前未删除子节点数量
• vis[u]：标记节点 $u$ 是否已被删除
• ucnt：累计已删除的节点总数
• tcnt：当前时刻可被删除的叶子节点数量

算法流程

int solve(int n, int m, std::vector<int> fa, std::vector<std::vector<int>> s) {
    // 初始化
    for (int u = 0; u < n; ++u)
        ch[u] = vis[u] = 0;
    
    // 统计每个节点的子节点数
    for (int u = 1; u < n; ++u)
        ++ch[fa[u]];
    
    int ucnt = 0, tcnt = 0, ans = 0;
    
    // 处理每个记录位置
    for (int i = 0; i < n - 1; ++i) {
        // 处理所有志愿者在该位置的记录
        for (int j = 0; j < m; ++j) {
            int u = s[j][i];
            
            if (!vis[u]) {
                // 标记节点为已删除
                vis[u] = true;
                // 减少父节点的未删除子节点数
                --ch[fa[u]];
                
                // 如果当前节点是叶子，增加可删除叶子数
                if (ch[u] == 0)
                    ++tcnt;
                
                // 如果父节点变为叶子且未被删除，增加可删除叶子数
                if (ch[fa[u]] == 0 && vis[fa[u]])
                    ++tcnt;
                
                ++ucnt;
            }
        }
        
        // 判断是否可以结束一天
        if (ucnt == i + 1 && tcnt == i + 1)
            ++ans;
    }
    
    return ans;
}

算法正确性证明

关键条件分析

1. ucnt == i + 1：

   • 确保所有扫描到的节点都已被删除
   • 表示处理了前 $i+1$ 个位置的所有节点

2. tcnt == i + 1：

   • 确保当前可删除的叶子数等于已删除节点数
   • 这意味着所有已删除的节点在删除时都是叶子节点

为什么这样能得到最大天数？

当 ucnt == i + 1 && tcnt == i + 1 时，说明：

• 所有已删除节点都是合法删除的（删除时是叶子）
• 没有违反任何父子约束关系
• 志愿者记录的顺序约束得到满足

此时可以安全地结束当前天，开始新的一天，从而最大化总天数。

时间复杂度分析

• 初始化：$O(N)$
• 处理记录：$O(NM)$
• 总复杂度：$O(NM)$

由于题目约束 $\sum NM \leq 8 \times 10^5$，该复杂度完全可接受。

样例详解

样例 1

输入: N=3, M=1, F=[-1,0,0], S=[[1,2]]
处理过程:
i=0: u=1, ch[0]=1→0, tcnt=1, ucnt=1 → ans=1
i=1: u=2, ch[0]=0→-1, tcnt=2, ucnt=2 → ans=2
输出: 2

样例 2

输入: N=5, M=2, F=[-1,0,0,1,1], S=[[1,2,3,4],[4,1,2,3]]
处理过程:
由于记录间的矛盾，某些节点必须在同一天删除
最终只能得到 ans=1
输出: 1

算法优势

1. 简洁高效：线性时间复杂度，易于实现
2. 正确性强：严格维护叶子删除的合法性
3. 空间优化：仅使用 $O(N)$ 的额外空间

总结

本题通过巧妙维护当前可删除叶子数量和已删除节点数量的平衡，在满足所有约束条件的前提下求出最大可能的天数。算法核心在于识别那些可以安全结束当前天的时刻，从而将落叶过程分散到尽可能多的天数中。