「COCI 2023.2」Mreža 题解

题目大意

给定一棵 $n$ 个节点的树，每条边有三个属性：

• $v_i$：当前速度
• $c_i$：升级花费
• $s_i$：升级后速度

有 $q$ 个查询，每个查询给出 $a_i, b_i, e_i$，要求从 $a_i$ 到 $b_i$ 的路径上选择一些边升级，使得：

• 总花费不超过 $e_i$
• 路径上的最小速度最大化

解题思路

核心观察

1. 问题转化：在树上路径上选择边升级，使得最小速度最大
2. 贪心策略：优先升级那些升级后能显著提高最小速度的边
3. 可持久化数据结构：需要快速查询路径信息

算法概述

1. 树链剖分预处理

void dfs1(int u, int f) {
    fa[u] = f; dep[u] = dep[f] + 1; size[u] = 1;
    // 计算子树大小，找重儿子
}

void dfs2(int u, int f) {
    top[u] = f;
    // 构建重链
}

• 用于快速计算 LCA 和处理路径查询

2. 可持久化线段树

class treenode_t {
public:
    int64_t sum;  // 花费总和
    int ls, rs, cnt;  // 左右儿子，计数
};

每个节点维护一个线段树，存储从根到该节点路径上的边信息。

3. 关键操作

插入边信息：

void modify(int &x, int l, int r, int p, int v, int c) {
    // 在位置p插入信息：花费v，计数c
    // 构建可持久化版本
}

查询处理：

int query(int x, int y, int z, int l, int r, int64_t k) {
    // 利用可持久化线段树求路径信息
    // x: 节点a的根, y: 节点b的根, z: lca的根
    // k: 剩余预算
}

算法流程

1. 预处理：

   • 树链剖分计算 LCA
   • 离散化所有速度值
   • 构建可持久化线段树

2. 查询处理：

   • 对于查询 $(a, b, e)$，找到 LCA $c$
   • 在可持久化线段树上查询：

     query(rt[a], rt[b], rt[c], 1, len, e)
     

   • 返回对应的速度值

查询策略详解

线段树按速度值离散化后建立，每个节点维护：

• sum：该速度区间内所有边的升级花费总和
• cnt：该速度区间内边的数量

查询时从高速度往低速度遍历：

• 如果当前速度区间的边都能用剩余预算升级，则升级并继续向更高速度探索
• 否则停留在当前速度区间

这实际上是一个二分答案的过程，但通过线段树优化为 $O(\log n)$。

关键代码解析

可持久化线段树构建

void dfs3(int u) {
    for (auto &e : E[u]) {
        int v = e.v;
        if (v == fa[u]) continue;
        
        // 离散化速度值
        int v1 = std::lower_bound(o + 1, o + len + 1, e.val1) - o;
        int v2 = std::lower_bound(o + 1, o + len + 1, e.val2) - o;
        
        // 继承父节点的线段树
        rt[v] = rt[u];
        
        // 插入当前边的信息
        modify(rt[v], 1, len, v1, e.cost, 0);  // 原速度边的花费
        modify(rt[v], 1, len, v2, 0, 1);       // 升级后速度边的计数
        dfs3(v);
    }
}

路径查询

int query(int x, int y, int z, int l, int r, int64_t k) {
    if (l == r) return l;
    
    int mid = (l + r) >> 1;
    // 计算左子树（高速度区间）的合并信息
    int64_t ss = t[t[x].ls].sum + t[t[y].ls].sum - t[t[z].ls].sum * 2;
    int cc = t[t[x].ls].cnt + t[t[y].ls].cnt - t[t[z].ls].cnt * 2;
    
    if (cc > 0 || k < ss)
        // 如果还有边可以升级或预算不够，继续探索高速度区间
        return query(t[x].ls, t[y].ls, t[z].ls, l, mid, k);
    else
        // 否则探索低速度区间
        return query(t[x].rs, t[y].rs, t[z].rs, mid + 1, r, k - ss);
}

复杂度分析

• 预处理：
  • 树链剖分：$O(n)$
  • 可持久化线段树：$O(n \log n)$
• 每个查询：$O(\log n)$
• 总复杂度：$O((n + q) \log n)$

样例验证

样例1查询1：$a=2, b=4, e=15$

• 路径：$2 \to 1 \to 3 \to 4$
• 算法会找到最优解：升级 $(2,1)$ 和 $(1,3)$，最小速度 $7$
• 输出：7

样例1查询2：$a=6, b=4, e=5$

• 路径：$6 \to 3 \to 4$
• 只能升级 $(3,4)$，最小速度 $5$
• 输出：5

总结

本题的解法巧妙结合了：

1. 树链剖分：快速处理路径查询
2. 可持久化线段树：维护路径上的边信息
3. 离线离散化：处理大值域
4. 贪心策略：优先升级高速度边

通过可持久化数据结构，将路径查询转化为区间查询，实现了高效的问题求解。