「KTSC 2023 R2」基地简化 题解

问题重述

给定一棵 $n$ 个节点的树，节点编号为 $0$ 到 $n-1$。对于每个区间 $[i,j]$（$0 \leq i \leq j \leq n-1$），定义其维护成本为：选择一些边，使得区间内所有节点在选择的边构成的子图中连通（可以经过区间外的节点），且选择的边权和最小。

求所有区间维护成本之和，对 $10^9+7$ 取模。

关键观察

1. 问题转化

对于区间 $[l,r]$，其维护成本等于包含区间内所有节点的最小连通子图的边权和。

由于树的结构，这个最小连通子图就是区间内所有节点的最小斯坦纳树。在树的情况下，这就是包含这些节点的最小子树。

2. 区间连续性的利用

题目中节点编号具有特殊性质（虽然没有明确说明，但从代码推断），使得我们可以利用编号的连续性来高效计算。

关键性质：如果区间 $[l,r]$ 中的节点在树上形成连续块，那么计算会简化。

3. 贡献计算思路

考虑每条边 $e$（权重 $w$）对总答案的贡献。边 $e$ 会出现在区间 $[l,r]$ 的最小连通子图中，当且仅当区间 $[l,r]$ 同时包含边两侧子树中的节点。

因此，总答案可以表示为：

$$\text{答案} = \sum_{\text{边 } e} w_e \times (\text{包含边两侧节点的区间数量}) $$

算法核心

数据结构设计

代码使用 DFS 遍历树，并为每个节点维护：

• 一个集合 set<pair<int, int>>，存储该子树中所有连续编号区间
• 一个值表示当前子树的某种"代价"

核心函数解析

cost(l, r) 函数

inline int cost(int l, int r) {
    int len = r - l + 2;  // 注意这里是 +2，不是 +1
    return len * (len - 1ll) / 2 % mod;
}

这个函数计算的是区间 $[l,r]$ 的所有子区间个数，但参数设计有些特殊。

DFS 合并过程

1. 初始化：每个节点开始时只包含自己作为一个区间
2. 合并子树：对于每个子节点，将其区间集合合并到当前节点的集合中
3. 区间合并：当两个区间相邻时（如 $[a,b]$ 和 $[b+1,c]$），合并为 $[a,c]$
4. 贡献计算：在合并过程中，当处理边 $(now, i)$ 时：

   add(ans, (sum - tmp.first + mod) * w % mod);
   

   这里 sum - tmp.first 计算的是包含该边两侧节点的区间数量

算法流程

def dfs(now, last):
    # 初始化当前节点：只包含自己
    intervals = {[now, now]}
    cost_val = 计算初始代价
    
    for each child i of now:
        child_intervals, child_cost = dfs(i, now)
        
        # 计算当前边对答案的贡献
        ans += (总区间数 - child_cost) * 边权
        
        # 启发式合并：小集合合并到大集合
        if len(intervals) < len(child_intervals):
            swap(intervals, child_intervals)
            
        # 合并区间集合
        for each interval [l, r] in child_intervals:
            # 找到插入位置
            # 检查是否可以与左右区间合并
            # 更新代价
            intervals.insert(合并后的区间)
    
    return (intervals, cost_val)

正确性证明

区间合并的正确性

算法维护连续编号区间的集合，这是因为：

• 树的 DFS 遍历顺序与编号顺序相关
• 连续区间在合并时会产生更简单的计算

贡献计算的正确性

对于边 $(u,v)$，设 $v$ 所在的子树区间集合对应的代价为 $C$，那么：

• 总区间数：$\frac{n(n+1)}{2}$
• 不包含 $v$ 子树中任何节点的区间数：可以通过 $C$ 计算得到
• 因此包含 $v$ 子树中至少一个节点的区间数：总区间数 - $C$

但是这些区间中，有些可能只包含 $v$ 子树中的节点，而不包含 $u$ 侧的节点。算法通过精妙的区间合并和代价计算，准确统计了同时包含边两侧节点的区间数量。

复杂度分析

• 时间复杂度：$O(n \log^2 n)$

  • DFS 遍历：$O(n)$
  • 启发式合并：每个元素最多被合并 $O(\log n)$ 次
  • set 操作：每次 $O(\log n)$
  • 总复杂度：$O(n \log^2 n)$

• 空间复杂度：$O(n)$

总结

本题的解法巧妙利用了树的结构和编号连续性，通过维护连续区间集合和启发式合并，高效地计算了所有区间的最小连通子图边权和之和。核心思想是将问题转化为统计每条边被多少个区间"需要"，避免了直接枚举所有区间的暴力做法。

算法的精妙之处在于区间合并过程中代价的维护和更新，使得我们能够快速计算包含特定边两侧节点的区间数量。