题解

问题分析

我们需要将一棵树上的节点分配到若干段中，使得：

1. 同一段中的节点不能有祖先-后代关系
2. 段的大小是该段中所有节点权值的最大值
3. 最小化所有段大小的和

关键观察

这个问题可以转化为：我们需要为每个节点分配一个段，使得在树的任何一条根到叶子的路径上，同一个段最多出现一次。

贪心策略

核心思想

使用自底向上的贪心策略，合并子树的信息：

1. 叶子节点：每个叶子单独形成一个段，值为该节点的权值
2. 内部节点：将子树的段列表与当前节点合并
3. 合并规则：将各子树的段按值从大到小配对，取最大值

算法步骤

void fake_main() {
    n = read();
    rep(i, 1, n) a[i] = read();
    rep(i, 2, n) fa[i] = read();
    
    // 自底向上处理
    per(i, n, 1) {
        s[i].insert(a[i]);  // 当前节点自身形成一个段
        
        if (i == 1) continue;
        
        // 启发式合并：总是将小的集合合并到大的集合中
        if (s[fa[i]].size() < s[i].size())
            s[fa[i]].swap(s[i]);
        
        multiset<int> tmp;
        
        // 关键步骤：配对合并
        while (!s[i].empty()) {
            auto it1 = prev(s[i].end()), it2 = prev(s[fa[i]].end());
            tmp.insert(max(*it1, *it2));  // 取两个段的最大值
            s[i].erase(it1), s[fa[i]].erase(it2);
        }
        
        // 将合并结果放回父节点的集合
        while (!tmp.empty()) {
            auto it = tmp.begin();
            s[fa[i]].insert(*it);
            tmp.erase(it);
        }
    }
    
    // 计算根节点所有段的和
    int sum = 0;
    for (int i : s[1]) sum += i;
    write(sum);
}

算法正确性证明

为什么这样合并是有效的？

1. 路径约束保证：在任意根到叶子的路径上，我们通过配对合并确保了同一段不会出现两次
2. 最优性保证：每次合并时，我们将较大的段与较大的段配对，这样可以最小化最终的和
3. 无后效性：子树的信息完全包含在它们的段集合中，父节点只需要这些集合而不需要子树的结构信息

时间复杂度分析

• 使用 multiset 存储每个节点的段集合
• 采用启发式合并，确保总时间复杂度为 $O(n \log^2 n)$
• 每个元素最多被合并 $O(\log n)$ 次，每次合并操作 $O(\log n)$

数学建模

设 $f(u)$ 表示以 $u$ 为根的子树的最优段集合。那么：

• 对于叶子节点：$f(u) = \{a_u\}$
• 对于内部节点：$f(u) = \text{merge}(\{a_u\}, f(v_1), f(v_2), \dots, f(v_k))$

其中 $\text{merge}$ 操作就是上述的配对合并过程。

总结

这个问题的核心在于认识到：

1. 问题可以转化为路径约束下的段分配
2. 使用自底向上的树形DP思想
3. 通过巧妙的配对合并策略保证最优性
4. 使用启发式合并来优化时间复杂度

该算法优雅地解决了这个看似复杂的问题，体现了贪心思想在树形结构上的巧妙应用。