「KTSC 2023 R1」出租车旅行 题解

题目大意

给定一棵 $n$ 个节点的树，节点编号为 $0$ 到 $n-1$，其中 $0$ 号节点是首都。每个节点 $i$ 有一辆出租车，计费方式为：基本费用 $A[i]$ 元 + 每公里 $B[i]$ 元。

从首都出发前往各个城市，可以在任意城市换乘出租车。求从首都到达每个其他城市的最小费用。

数据范围：$n \leq 10^5$

算法思路

问题分析

设 $f[i]$ 表示到达城市 $i$ 的最小费用，则状态转移方程为：

$$f[j] = \min\{f[i] + A[i] + B[i] \times dist(i,j)\} $$

这可以看作：对于每个城市 $i$，它提供了一条"出租车线路"：

$$cost_j = f[i] + A[i] + B[i] \times dist(i,j)$$

我们需要快速找到对于每个 $j$，所有线路中的最小值。

关键观察

将费用公式重写：

$$cost_j = B[i] \times dist(i,j) + (f[i] + A[i])$$

这是一个关于距离的一次函数，斜率为 $B[i]$，截距为 $f[i] + A[i]$。

问题转化为：在树上维护多个一次函数，支持快速查询在给定距离处的最小函数值。

核心算法：点分治 + 凸包优化

1. 点分治分解

将树分解为点分树，使得：

• 树高为 $O(\log n)$
• 任意两点路径在点分树上有 $O(\log n)$ 个公共重心

void findrt(int x, int prt) {
    sz[x] = 1;
    int mx = 0;
    for (auto [y, w] : e[x])
        if (y != prt && !v[y])
            findrt(y, x), sz[x] += sz[y], mx = max(mx, sz[y]);
    mx = max(mx, all - sz[x]);
    if (mx < mi) mi = mx, rt = x;
}

2. 凸包维护

对于每个重心，维护其管辖范围内所有出租车线路的下凸壳：

struct line {
    ll k, b;  // y = k*x + b
    ll calc(ll x) { return k * x + b; }
};

void insert(int x, line v) {
    // 维护下凸壳：删除不优的直线
    while (stk[x].size() > 1 && check(stk[x][stk[x].size()-2], stk[x].back(), v))
        stk[x].pop_back();
    if (stk[x].empty() || stk[x].back().k != v.k)
        stk[x].push_back(v);
}

3. 查询优化

在凸包上二分查找最小值：

ll ask(int x, ll d) {
    if (stk[x].empty()) return 5e18;
    int l = 1, r = stk[x].size()-1, pos = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(stk[x][mid-1], stk[x][mid], d))
            pos = mid, l = mid + 1;
        else r = mid - 1;
    }
    return stk[x][pos].calc(d);
}

算法流程

$1.$ 预处理：构建点分树，预处理LCA

$2.$ 排序：按 $B[i]$ 降序排序，保证凸包性质

$3.$ 动态规划：按排序顺序处理每个城市：

• 查询到达该城市的最小费用
• 将该城市的出租车线路加入凸包

$4.$ 输出：查询每个目标城市的最小费用

vector<long long> travel(vector<long long> A, vector<int> B, vector<int> U, vector<int> V, vector<int> W) {
    // 初始化建图
    n = A.size();
    for (int i = 0; i < n; i++)
        a[i+1] = A[i], b[i+1] = B[i];
    
    // 构建点分树
    dfs1(1, 0);
    mi = all = n;
    findrt(1, 0);
    dfs2(rt);
    
    // 按斜率排序
    for (int i = 1; i <= n; i++) p[i] = i;
    sort(p + 1, p + 1 + n, [&](int x, int y) {
        return b[x] > b[y];
    });
    
    // 动态规划
    for (int i = 1; i <= n; i++) {
        int x = p[i];
        ll d = query(x);  // 在点分树上查询最小值
        if (x == 1) d = 0;  // 起点
        if (d != 5e18)
            add(x, {b[x], d + a[x]});  // 加入新线路
    }
    
    // 输出结果
    vector<ll> res;
    for (int i = 2; i <= n; i++)
        res.push_back(query(i));
    return res;
}

关键技巧详解

1. 点分治的优势

• 平衡结构：点分树高 $O(\log n)$
• 路径覆盖：任意路径被 $O(\log n)$ 个重心覆盖
• 局部处理：每个重心只处理其管辖范围内的信息

2. 凸包优化的原理

对于一次函数集合，最小值函数构成一个下凸壳。插入新直线时：

• 斜率大的直线在右侧更优
• 斜率小的直线在左侧更优
• 需要维护凸壳的单调性

3. 斜率排序的重要性

按 $B[i]$ 降序插入保证：

• 新直线的斜率不会大于凸壳中现有直线
• 维护凸壳的复杂度为均摊 $O(1)$

复杂度分析

• 时间复杂度：$O(n \log^2 n)$
  • 点分治构建：$O(n \log n)$
  • 每个点查询/更新：$O(\log^2 n)$（点分树 $O(\log n)$ 层 × 凸包操作 $O(\log n)$）
• 空间复杂度：$O(n \log n)$

总结

本题通过将问题转化为树上一次函数最小值查询，结合点分治和凸包优化两种高级技巧，在 $O(n \log^2 n)$ 时间内解决了大规模树上的动态规划问题。这种"分治+凸包"的思路在解决类似的树形DP问题时具有很好的通用性。