「CEOI2024」加油站 题解

题目分析

给定一棵 $N$ 个节点的树，每条边有长度 $l_i$。对于每个有序节点对 $(a,b)$，有一辆车从 $a$ 出发到 $b$，油箱容量为 $K$，每公里消耗 $1$ 升油。车辆只在油量不足以到达下一城市时才加油，且加油时加满油箱。要求计算每个加油站的加油车辆数。

算法思路

本解法采用点分治策略，通过分治处理树上的路径问题，利用二分查找和前缀和优化统计过程。

核心思想

对于点分治的当前根节点 $rt$，考虑所有经过 $rt$ 的路径 $(u,v)$。我们需要统计在这些路径中，哪些节点需要加油。

关键观察

1. 加油条件：车辆在节点 $u$ 加油，当且仅当从上一个加油站到 $u$ 的路径长度 $> K$
2. 点分治优势：将路径分为经过根节点的路径，分别处理各个子树
3. 统计技巧：利用深度信息和二分查找确定加油位置

代码实现详解

数据结构和变量定义

const int N = 7 * 1e4 + 100;
int n, k, sz[N], num[N], dep[N], f[N], g[N], anc[N], sum[N], top;
vector<pii> G[N];  // 邻接表存储树
bitset<N> vis;      // 标记点分治中已处理的节点
map<int, int> nrt;  // 按深度存储计数信息

• sz[u]: 子树大小
• num[u]: 最终答案，在节点 $u$ 加油的车辆数
• dep[u]: 节点 $u$ 到当前根节点的距离
• f[u]: 临时统计量
• g[u]: 另一临时统计量
• anc[]: 存储当前路径的祖先节点
• sum[]: 前缀和数组

点分治主框架

void solve(int cur, int tot) {
    // 1. 寻找重心作为根节点
    int rt = get_rt(cur, 0, tot).rp;
    vis[rt] = 1;
    dep[rt] = 0;
    init(rt, 0);
    
    // 2. 初始化祖先数组和映射表
    anc[top = 1] = rt;
    sum[1] = 0;
    nrt.clear();
    nrt[k]++;  // 根节点特殊处理
    
    // 3. 第一遍DFS：统计子树信息
    for (auto i : G[rt])
        if (!vis[i.lp])
            dfs1(i.lp, rt, tot - sz[i.lp]);
    
    // 4. 计算前缀和
    into_sum();
    
    // 5. 第二遍DFS：计算g数组
    for (auto i : G[rt])
        if (!vis[i.lp])
            dfs2(i.lp, rt);
    
    // 6. 第三、四遍DFS：最终统计
    for (auto i : G[rt])
        if (!vis[i.lp])
            nrt.clear(), dfs3(i.lp, rt), into_sum(), dfs4(i.lp, rt);
    
    // 7. 递归处理子树
    for (auto i : G[rt])
        if (!vis[i.lp])
            solve(i.lp, sz[i.lp]);
}

关键函数详解

1. 寻找重心 get_rt

pii get_rt(int u, int frm, int tot) {
    pii ret = {inf, 0};
    int mxp = 0;
    sz[u] = 1;

    for (auto i : G[u]) {
        int v = i.lp;
        if (v == frm || vis[v]) continue;
        
        ret = min(ret, get_rt(v, u, tot));
        sz[u] += sz[v];
        mxp = max(mxp, sz[v]);
    }
    
    return min(ret, (pii){max(mxp, tot - sz[u]), u});
}

通过DFS计算子树大小，找到使最大子树最小的重心。

2. 第一遍DFS dfs1

void dfs1(int u, int frm, int tot) {
    anc[++top] = u;  // 记录当前路径
    
    // 递归处理子节点
    for (auto i : G[u])
        if (i.lp != frm && !vis[i.lp])
            dfs1(i.lp, u, tot);
    
    num[u] += tot * f[u];  // 累加贡献
    top--;  // 回溯
    
    // 根据深度判断加油位置
    if (k >= dep[u]) {
        // 可以在根节点加油的情况
        nrt[k - dep[u]] += f[u] + 1;
    } else {
        // 需要二分查找最近的加油位置
        int l = 1, r = top;
        while (l < r) {
            int mid = (l + r) / 2;
            if (dep[u] - dep[anc[mid]] <= k)
                r = mid;
            else
                l = mid + 1;
        }
        f[anc[l]] += f[u] + 1;  // 在祖先节点处加油
    }
}

3. 前缀和计算 into_sum

void into_sum() {
    for (auto i = next(nrt.begin()); i != nrt.end(); i++)
        i->rp += prev(i)->rp;
}

将映射表转换为前缀和形式，便于区间查询。

4. 第二遍DFS dfs2

void dfs2(int u, int frm) {
    for (auto i : G[u])
        if (i.lp != frm && !vis[i.lp])
            dfs2(i.lp, u);
    
    // 利用前缀和计算g[u]
    auto it1 = nrt.lower_bound(dep[u]);
    auto it2 = nrt.lower_bound(dep[frm]);
    
    if (it1 == nrt.begin())
        g[u] = 0;
    else if (it2 == nrt.begin())
        g[u] = prev(it1)->rp;
    else
        g[u] = prev(it1)->rp - prev(it2)->rp;
}

5. 最终统计 dfs3 和 dfs4

dfs3 重新构建映射表，dfs4 进行最终的数量统计：

void dfs4(int u, int frm) {
    // 调整g[u]的值
    auto it1 = nrt.lower_bound(dep[u]);
    auto it2 = nrt.lower_bound(dep[frm]);
    // ... 计算逻辑类似dfs2
    
    // 二分查找确定加油区间
    if (dep[anc[1]] < dep[u] - k && dep[frm] - k <= dep[anc[top - 1]]) {
        // 使用二分查找确定边界
        int l = 1, r = top - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (dep[anc[mid]] < dep[u] - k)
                l = mid;
            else
                r = mid - 1;
        }
        g[u] += sum[l + 1];  // 累加前缀和
        
        // 另一个二分查找
        l = 1, r = top - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (dep[frm] - k <= dep[anc[mid]])
                r = mid;
            else
                l = mid + 1;
        }
        g[u] -= sum[l];  // 减去多余部分
    }
    
    // 更新祖先路径和前缀和
    anc[++top] = u;
    sum[top] = sum[top - 1] + g[u];
    
    // 递归处理子节点
    for (auto i : G[u])
        if (i.lp != frm && !vis[i.lp])
            dfs4(i.lp, u);
    
    // 回溯
    top--;
    num[frm] += sz[u] * g[u];  // 累加到父节点的答案
}

复杂度分析

• 点分治：$O(N \log N)$ 层递归
• 每层处理：DFS遍历 $O(N)$，二分查找 $O(\log N)$，映射表操作 $O(\log N)$
• 总复杂度：$O(N \log^2 N)$

总结

本解法通过点分治将问题分解，利用深度信息和二分查找确定加油位置，使用前缀和优化统计过程。代码实现较为复杂，但能够高效处理大规模数据，符合题目要求。