「RMI 2018」Traffickers 题解

有 $N$ 个城市的树，初始有 $K$ 个贩运者，每个贩运者在 $(u,v)$ 之间周期性移动：

• 从时间 $0$ 开始，从 $u$ 沿最短路径到 $v$
• 每个整数时间点在当前位置交付 1 单位货物
• 到达 $v$ 后，下一个时间点瞬间传送到 $u$，继续循环

有三种操作：

1. 添加贩运者 $(u,v)$
2. 删除贩运者 $(u,v)$（保证存在）
3. 查询：在时间 $[t_1, t_2]$ 内，所有贩运者在路径 $u_q \to v_q$ 上交付的货物总数

关键性质分析

1. 贩运者运动规律

设贩运者在 $(u,v)$ 之间移动，树上的距离为 $d = \text{dist}(u,v)$。

• 周期 $T = 2d$
• 在时间 $t$，位置由 $r = t \mod T$ 决定：
  • 如果 $0 \leq r \leq d$：在从 $u$ 到 $v$ 的路上，距离 $u$ 为 $r$
  • 如果 $d < r < T$：在从 $v$ 回 $u$ 的路上，距离 $v$ 为 $r-d$

2. 路径交集

对于贩运者路径 $P_t = u \to v$ 和查询路径 $P_q = u_q \to v_q$，它们的交集 $I = P_t \cap P_q$ 是树上的一个路径（可能为空）。

由于树结构，两条路径的交集可以高效计算：

1. 找到 $P_t$ 和 $P_q$ 的公共部分
2. 交集要么为空，要么是一条连续路径

3. 时间区间内的计数

我们需要计算：在时间 $[t_1, t_2]$ 内，贩运者在交集 $I$ 上的时间点数量。

设交集 $I$ 在贩运者路径上的位置：从距离 $u$ 为 $a$ 到 $b$（$0 \leq a \leq b \leq d$）。

贩运者在时间 $t$ 在 $I$ 上当且仅当：

• $t \mod T \in [a, b] \cup [T-b, T-a]$

解决方案

第一步：树预处理

使用 LCA（最近公共祖先）预处理，支持：

• 快速计算两点距离 $\text{dist}(u,v)$
• 快速计算路径交集

class Tree {
    int n;
    vector<vector<int>> adj;
    vector<int> depth, parent[20]; // 倍增数组
    
    void dfs(int u, int p) {
        parent[0][u] = p;
        for (int v : adj[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
    
public:
    Tree(int n) : n(n), adj(n+1), depth(n+1) {
        for (int i = 0; i < 20; i++) parent[i].resize(n+1);
    }
    
    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void build() {
        depth[1] = 0;
        dfs(1, 0);
        for (int i = 1; i < 20; i++) {
            for (int u = 1; u <= n; u++) {
                parent[i][u] = parent[i-1][parent[i-1][u]];
            }
        }
    }
    
    int lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        // 提升u到与v同一深度
        for (int i = 19; i >= 0; i--) {
            if (depth[u] - (1 << i) >= depth[v]) {
                u = parent[i][u];
            }
        }
        if (u == v) return u;
        // 同时提升
        for (int i = 19; i >= 0; i--) {
            if (parent[i][u] != parent[i][v]) {
                u = parent[i][u];
                v = parent[i][v];
            }
        }
        return parent[0][u];
    }
    
    int dist(int u, int v) {
        int w = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[w];
    }
    
    // 判断点x是否在路径u-v上
    bool on_path(int u, int v, int x) {
        int w = lca(u, v);
        return (on_path_segment(u, w, x) || on_path_segment(v, w, x));
    }
    
    // 获取路径u-v上的所有点
    vector<int> get_path(int u, int v) {
        int w = lca(u, v);
        vector<int> path;
        // 从u到w
        while (u != w) {
            path.push_back(u);
            u = parent[0][u];
        }
        path.push_back(w);
        // 从w到v（不包括w）
        vector<int> right;
        while (v != w) {
            right.push_back(v);
            v = parent[0][v];
        }
        reverse(right.begin(), right.end());
        path.insert(path.end(), right.begin(), right.end());
        return path;
    }
};

第二步：计算路径交集

对于贩运者路径 $P_t = u_t \to v_t$ 和查询路径 $P_q = u_q \to v_q$，我们需要找到它们的交集。

// 计算两条路径的交集在贩运者路径上的位置
pair<int, int> get_intersection_range(Tree &tree, int u_t, int v_t, int u_q, int v_q) {
    int d = tree.dist(u_t, v_t);
    
    // 获取贩运者路径上的所有点
    vector<int> path_t = tree.get_path(u_t, v_t);
    
    // 找到交集端点
    int a = -1, b = -1;
    for (int i = 0; i < path_t.size(); i++) {
        int node = path_t[i];
        if (tree.on_path(u_q, v_q, node)) {
            if (a == -1) a = i;
            b = i;
        }
    }
    
    if (a == -1) return {-1, -1}; // 无交集
    
    return {a, b};
}

第三步：计算单个贩运者在时间区间内的贡献

// 计算在时间[t1, t2]内，满足 t mod T ∈ S 的整数t的数量
long long count_in_range(long long t1, long long t2, long long T, long long a, long long b) {
    if (a > b) return 0;
    
    // S = [a, b] ∪ [T-b, T-a]
    long long total = 0;
    
    // 函数：计算在[l, r]内满足条件的数量
    auto count_segment = [&](long long l, long long r, long long L, long long R) -> long long {
        if (l > r || L > R) return 0;
        // 调整到模T的范围内
        l = max(l, 0LL);
        r = min(r, t2);
        if (l > r) return 0;
        
        // 计算完整周期
        long long first_complete = (l + T - 1) / T * T;
        long long last_complete = (r / T) * T;
        
        if (first_complete > last_complete) {
            // 没有完整周期，直接计算
            long long cnt = 0;
            for (long long t = l; t <= r; t++) {
                long long r_mod = t % T;
                if (L <= r_mod && r_mod <= R) cnt++;
            }
            return cnt;
        }
        
        // 完整周期数
        long long cycles = (last_complete - first_complete) / T + 1;
        // 每个周期中满足条件的数量
        long long per_cycle = max(0LL, R - L + 1);
        
        total = cycles * per_cycle;
        
        // 加上左边不完整部分
        for (long long t = l; t < first_complete; t++) {
            long long r_mod = t % T;
            if (L <= r_mod && r_mod <= R) total++;
        }
        
        // 加上右边不完整部分
        for (long long t = last_complete + 1; t <= r; t++) {
            long long r_mod = t % T;
            if (L <= r_mod && r_mod <= R) total++;
        }
        
        return total;
    };
    
    long long cnt1 = count_segment(t1, t2, a, b);
    long long cnt2 = count_segment(t1, t2, T - b, T - a);
    
    return cnt1 + cnt2;
}

第四步：数据结构优化

由于 $Q \leq 50000$，$K \leq 50000$，我们不能对每个查询都遍历所有贩运者。

关键观察：路径长度最多 20，所以周期 $T \leq 38$。

我们可以按周期分组：

class TraffickerSystem {
    int n;
    Tree tree;
    // 按周期分组存储贩运者
    vector<map<pair<int, int>, int>> traffickers_by_period;
    
public:
    TraffickerSystem(int n) : n(n), tree(n) {
        // 周期最大为 38（因为路径最多20个城市，距离最大19，周期=2*19=38）
        traffickers_by_period.resize(39);
    }
    
    void add_trafficker(int u, int v) {
        int d = tree.dist(u, v);
        int T = 2 * d;
        traffickers_by_period[T][{min(u, v), max(u, v)}]++;
    }
    
    void remove_trafficker(int u, int v) {
        int d = tree.dist(u, v);
        int T = 2 * d;
        auto key = make_pair(min(u, v), max(u, v));
        traffickers_by_period[T][key]--;
        if (traffickers_by_period[T][key] == 0) {
            traffickers_by_period[T].erase(key);
        }
    }
    
    long long query(int u_q, int v_q, long long t1, long long t2) {
        long long total = 0;
        
        // 遍历所有可能的周期
        for (int T = 2; T <= 38; T += 2) { // 周期都是偶数
            for (auto &[pair_uv, count] : traffickers_by_period[T]) {
                int u_t = pair_uv.first, v_t = pair_uv.second;
                
                // 计算交集范围
                auto [a, b] = get_intersection_range(tree, u_t, v_t, u_q, v_q);
                if (a == -1) continue; // 无交集
                
                // 计算贡献
                long long d = T / 2; // 原距离
                long long contrib = count_in_range(t1, t2, T, a, b);
                total += contrib * count;
            }
        }
        
        return total;
    }
};

第五步：进一步优化查询

上面的查询仍然是 $O(38 \times \text{贩运者数})$，最坏情况下 $50000 \times 50000$ 不可行。

优化：对于每个查询路径 $u_q \to v_q$，预处理它与所有可能贩运者路径的交集信息。

由于路径长度有限（≤20），我们可以：

1. 将查询路径 $P_q$ 上的所有点提取出来（最多20个）
2. 对于每个贩运者，快速判断是否与 $P_q$ 有交集

但更好的方法是使用树链剖分+线段树：

// 使用树链剖分将树映射到线段树上
class HeavyLightDecomposition {
    int n;
    Tree &tree;
    vector<int> parent, depth, heavy, head, pos;
    int cur_pos;
    
    int dfs_hld(int u) {
        int size = 1, max_subtree = 0;
        for (int v : tree.adj[u]) {
            if (v == parent[u]) continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            int subtree_size = dfs_hld(v);
            size += subtree_size;
            if (subtree_size > max_subtree) {
                max_subtree = subtree_size;
                heavy[u] = v;
            }
        }
        return size;
    }
    
    void decompose(int u, int h) {
        head[u] = h;
        pos[u] = cur_pos++;
        if (heavy[u] != -1) {
            decompose(heavy[u], h);
        }
        for (int v : tree.adj[u]) {
            if (v != parent[u] && v != heavy[u]) {
                decompose(v, v);
            }
        }
    }
    
public:
    HeavyLightDecomposition(int n, Tree &tree) : n(n), tree(tree), 
        parent(n+1), depth(n+1), heavy(n+1, -1),
        head(n+1), pos(n+1), cur_pos(0) {}
    
    void build() {
        dfs_hld(1);
        decompose(1, 1);
    }
    
    // 查询路径u-v上的信息
    template<typename F>
    void query_path(int u, int v, F &&process) {
        for (; head[u] != head[v]; v = parent[head[v]]) {
            if (depth[head[u]] > depth[head[v]]) swap(u, v);
            process(pos[head[v]], pos[v]);
        }
        if (depth[u] > depth[v]) swap(u, v);
        process(pos[u], pos[v]);
    }
};

第六步：完整算法框架

1. 读入N，构建树，预处理LCA和HLD
2. 读入K个初始贩运者，加入系统
3. 对于每个查询Q：
   if type == 1: 添加贩运者
   if type == 2: 删除贩运者
   if type == 3: 计算并输出答案

第七步：复杂度分析

• 预处理：$O(N \log N)$
• 添加/删除贩运者：$O(\log N)$
• 查询：需要更复杂的分析

由于路径长度限制（≤20），我们可以设计更高效的查询算法。一个可能的方法是：

1. 对于每个贩运者 $(u,v)$，将其路径上的所有点存储
2. 对于查询路径 $P_q$，也提取所有点
3. 快速计算交集

但由于 $Q$ 和 $K$ 都很大，可能需要离线处理或分块算法。

算法标签

• 树结构：LCA、树链剖分、树上路径
• 数据结构：线段树、树状数组、分块
• 数论：周期性分析、模运算
• 动态维护：添加/删除操作
• 区间查询：时间区间内的计数

总结

本题是一道树上路径+周期性运动+动态维护的综合难题：

1. 核心：分析贩运者的周期性运动模式
2. 关键：高效计算路径交集和时间区间内的计数
3. 难点：在动态更新下处理大量查询
4. 突破口：路径长度限制使得周期很小，可以按周期分组处理

对于满分需要设计 $O((K+Q) \times \text{路径长度} \times \log N)$ 或更好的算法。在实际实现中，可能需要结合树链剖分、线段树维护区间信息，以及利用周期性进行数学优化。