「eJOI2022」Bounded Spanning Tree 题解

算法思路

本题使用树链剖分和贪心算法来解决带约束的最小生成树边权分配问题。核心思想是通过树链剖分处理路径约束，然后使用贪心策略为每条边分配满足条件的边权。

关键观察

1. MST约束条件

给定前 $n-1$ 条边构成MST，需要满足：

• 对于非树边 $(u,v)$，其边权必须大于 $u-v$ 路径上所有树边的边权
• 所有边权是 $[1,m]$ 的排列

2. 区间约束处理

每条边 $i$ 有边权范围 $[l_i, r_i]$，需要找到可行的分配方案。

代码解析

数据结构定义

int n, m, L[N], R[N], U[N], V[N], id[N], val[N], dn[N];
vector<pii> g[N];  // 邻接表存储树结构
set<int> s;        // 可用边权集合

树链剖分初始化

namespace HLD {
    int dfn[N], rnk[N], fa[N], top[N], dep[N];
    // 第一次DFS：计算子树大小和重儿子
    void dfs1(int u, int frm) {
        hson[u] = 0;
        sz[u] = 1;
        for (auto i : g[u]) {
            int v = i.lp, ie = i.rp;
            if (v == frm) continue;
            dfs1(v, u);
            sz[u] += sz[v];
            dn[ie] = v;  // 记录边对应的下方节点
            if (sz[hson[u]] < sz[v]) hson[u] = v;
        }
    }
    // 第二次DFS：建立DFS序和重链
    void dfs2(int u, int frm) {
        dfn[u] = ++dfncnt;
        rnk[dfncnt] = u;
        fa[u] = frm;
        dep[u] = dep[frm] + 1;
        top[u] = (u == hson[frm]) ? top[frm] : u;
        // ... 递归处理重儿子和轻儿子
    }
}

线段树维护

代码实现了两种线段树：

• segtree1：区间取min，单点查询（用于计算非树边的上限）
• segtree2：单点更新，区间查询max（用于维护路径上的最大边权）

主要算法流程

步骤1：计算非树边的上限

for (int i = n; i <= m; i++)
    HLD::upd_path(U[i], V[i], R[i]);
for (int i = 1; i < n; i++)
    R[i] = min(R[i], HLD::mx(dn[i]));  // 更新树边的实际上限

步骤2：贪心分配边权

sort(id + 1, id + m + 1, [&](int i, int j) {
    return (pii){R[i], i} < (pii){R[j], j};
});

for (int i = 1; i <= m; i++) {
    int cur = id[i], mn = 0;
    if (cur >= n)  // 非树边
        mn = HLD::mx_path(U[cur], V[cur]);  // 路径上最大边权
    
    auto it = s.lower_bound(L[cur]);
    while (it != s.end() && *it <= mn) it++;  // 跳过不满足条件的值
    
    if (it == s.end() || *it > R[cur])
        return printf("NO\n"), 0;  // 无解
        
    val[cur] = *it;
    s.erase(it);
    
    if (cur < n)  // 树边
        HLD::set(dn[cur], val[cur]);  // 更新到线段树
}

算法正确性

MST条件保证

• 树边分配：按 $R[i]$ 排序后贪心分配，确保后续边有足够的选择空间
• 非树边约束：非树边权值必须大于对应路径上所有树边的权值
• 区间约束：每个边权都在指定的 $[l_i, r_i]$ 范围内

贪心策略正确性

按 $R[i]$ 升序处理确保：

• 限制较紧的边优先选择
• 后续边有更大的选择空间

复杂度分析

• 树链剖分：$O(n \log n)$
• 线段树操作：每次 $O(\log n)$
• 排序：$O(m \log m)$
• 总复杂度：$O((n+m) \log n)$

关键技巧

1. 树链剖分：高效处理树上路径操作
2. 双线段树：分别处理区间min和区间max查询
3. 贪心排序：按右端点排序优化分配顺序
4. 集合维护：使用set快速查找可用边权