JOISC 2013 Day1 T3 「通信妨害」题解

我们有 $N$ 个村庄在 $x$ 轴上，坐标为 $(i,0)$。有两个通信系统：

• 系统1：有 $M_1$ 个枢纽，$y$ 坐标 > 0
• 系统2：有 $M_2$ 个枢纽，$y$ 坐标 < 0

每个系统都是一个树形结构（村庄和枢纽构成树），保证：

1. 每个系统内部所有节点都连通
2. 两个系统的树通过村庄连接（村庄是两个系统共有的叶子节点）

攻击由参数 $(A,B)$ 定义：

• 摧毁系统1中所有 $y > A$ 的枢纽（$A \ge 0$）
• 摧毁系统2中所有 $y < B$ 的枢纽（$B \le 0$）

给定 $Q$ 个查询 $A_q$，对于每个查询，求最大的 $B_q \le 0$，使得摧毁 $y > A_q$ 和 $y < B_q$ 的枢纽后，所有村庄之间仍然连通。

问题转化

关键观察

1. 连通性要求：所有村庄之间连通 ⇔ 村庄形成一棵生成树
2. 系统独立：每个系统本身是一棵树
3. 系统互补：当系统1的部分枢纽被摧毁时，系统2需要提供备用连接

更形式化的描述

设：

• $T_1$：系统1的树，包含村庄（叶子）和枢纽（内部节点）
• $T_2$：系统2的树，也包含相同的村庄

对于给定的 $A$：

• 删除 $T_1$ 中所有 $y > A$ 的节点（及相连的边）
• $T_1$ 被分割成若干连通块
• 我们需要 $T_2$ 提供连接，使得所有村庄连通

$B$ 的限制是：在 $T_2$ 中，我们可以删除 $y < B$ 的节点，但必须保留足够的节点使得村庄连通。

解决方案

第一步：系统1的分析

对于固定的 $A$，删除 $T_1$ 中 $y > A$ 的节点后，$T_1$ 会分裂成若干连通块。设这些连通块为 $C_1, C_2, \ldots, C_k$。

每个连通块 $C_i$ 包含一些村庄。我们需要系统2将这些连通块连接起来。

第二步：系统2的关键节点

在 $T_2$ 中，考虑所有枢纽按照 $y$ 坐标排序（从大到小，即从接近0到更负）。

定义 $need(A)$ 为：在系统1删除 $y > A$ 的枢纽后，为了连接所有村庄，在系统2中必须保留的枢纽集合（按 $y$ 坐标从大到小）。

更具体地说：

1. 将 $T_2$ 中所有枢纽按 $y$ 坐标从大到小排序
2. 从最接近0的枢纽开始，逐个检查：如果删除这个枢纽及所有 $y$ 更小的枢纽，村庄是否还能连通？
3. 找到第一个（$y$ 坐标最小）必须保留的枢纽

第三步：预处理关键信息

我们需要对每个可能的 $A$ 预处理对应的 $B$ 值。

关键技巧：将系统1的枢纽按 $y$ 坐标从大到小排序，然后依次"激活"它们。

设系统1枢纽按 $y$ 降序排列：$h_1, h_2, \ldots, h_{M_1}$，对应 $y$ 值为 $Y_1 \ge Y_2 \ge \cdots \ge Y_{M_1}$。

对于 $A$ 在区间 $(Y_{i+1}, Y_i]$ 时，系统1中只有 $h_1, \ldots, h_i$ 这些枢纽保留（$y > A$ 的被删除）。

第四步：连通块变化与系统2需求

当 $A$ 变化时，系统1的连通块会变化。我们可以用并查集维护：

• 初始时（$A$ 很大，所有枢纽都被删除）：每个村庄是独立的连通块
• 逐步添加枢纽（按 $y$ 降序）：每次添加一个枢纽会合并它连接的一些连通块

在系统1中，添加枢纽 $h_i$ 会将 $k$ 个连通块合并为1个。

第五步：系统2的 LCA 分析

在系统2中，为了连接某些村庄集合，我们需要保留这些村庄在 $T_2$ 中的 LCA（最低公共祖先）及其祖先。

设 $S$ 是需要连接的村庄集合。在 $T_2$ 中，连接 $S$ 中所有村庄所需的最小节点集合是 $S$ 的虚树节点集合。

重要性质：对于系统1的每个连通块 $C$，在系统2中需要保留 $C$ 中村庄的 LCA。

第六步：算法框架

1. 预处理系统1：

   • 按 $y$ 降序排序枢纽
   • 用并查集维护连通块
   • 记录每个连通块在系统2中对应的 LCA

2. 预处理系统2：

   • 构建树结构
   • 预处理 LCA（倍增或树链剖分）
   • 预处理每个节点的 $y$ 坐标

3. 处理查询：

   • 对每个 $A_q$，找到对应的连通块集合
   • 计算这些连通块在系统2中必须保留的枢纽
   • 找到其中 $y$ 坐标最小的枢纽，设其 $y$ 坐标为 $y_{\min}$
   • $B_q = y_{\min}$（因为所有 $y < y_{\min}$ 的都可以删除）

第七步：高效实现

由于 $N, M_1, M_2, Q$ 都可达 $10^5$，我们需要 $O((N+M)\log N)$ 或 $O(N\log N)$ 的算法。

数据结构设计：

1. 系统1处理：

   • 用并查集维护连通块
   • 每个连通块记录在系统2中的 LCA

2. 系统2处理：

   • 预处理欧拉序和深度，用于快速 LCA 查询
   • 对每个节点预处理子树中村庄集合

3. 查询处理：

   • 对 $A_q$ 排序，离线处理
   • 用指针扫描系统1枢纽

第八步：详细算法

1. 读入数据，构建两个系统的树
2. 对系统1枢纽按 y 降序排序
3. 对系统2：
   a. 预处理 LCA（倍增法，O(N log N)）
   b. 预处理每个节点的 y 坐标
4. 初始化并查集，每个村庄单独一个集合
   每个集合的 LCA 就是村庄本身
5. 预处理答案数组 ans[]，初始全为 0
6. 指针 i = 1（指向系统1枢纽列表）
7. 对查询按 A 降序排序
8. for each 查询 q (按 A 降序处理):
   while i <= M1 且 Y[i] > A[q]:
      添加枢纽 h_i：
        - 找到它连接的所有连通块
        - 合并这些连通块
        - 更新新连通块的 LCA（系统2中这些村庄的 LCA）
       i++
   
   当前系统1有 k 个连通块
   计算这些连通块的 LCA 在系统2中的最小 y 坐标
   ans[q] = 这个最小 y 坐标
9. 按原顺序输出 ans[]

第九步：正确性证明

1. 单调性：当 $A$ 减小时，系统1保留的枢纽变多，连通块变少，系统2需要保留的枢纽也变少（$B$ 变得更小）
2. 必要性：必须保留系统2中所有连通块的 LCA，否则对应的连通块无法连接
3. 充分性：保留这些 LCA 后，所有村庄都能通过系统2连接

第十步：时间复杂度

• 预处理：$O((N+M)\log N)$
• 并查集操作：$O(N\alpha(N))$
• 查询处理：$O((N+Q)\log N)$
• 总复杂度：$O((N+M+Q)\log N)$

代码实现要点

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int LOGN = 20;

struct System {
    int n, m;
    vector<pair<int, int>> hubs; // (x, y)
    vector<vector<int>> adj;
    
    void build() {
        adj.resize(n + m + 1);
        // 构建树...
    }
};

System sys1, sys2;
int N, M1, M2, Q;

// 系统2的LCA预处理
int depth[MAXN*2], parent[MAXN*2][LOGN];
int tin[MAXN*2], tout[MAXN*2], timer;

void dfs_lca(int u, int p) {
    tin[u] = ++timer;
    parent[u][0] = p;
    for (int i = 1; i < LOGN; i++)
        parent[u][i] = parent[parent[u][i-1]][i-1];
    
    for (int v : sys2.adj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs_lca(v, u);
    }
    tout[u] = ++timer;
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = LOGN-1; i >= 0; i--) {
        if (!is_ancestor(parent[u][i], v))
            u = parent[u][i];
    }
    return parent[u][0];
}

// 并查集
struct DSU {
    vector<int> parent;
    vector<int> lca_id; // 在系统2中的LCA
    
    DSU(int n) {
        parent.resize(n);
        lca_id.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            lca_id[i] = i; // 初始每个村庄的LCA是自己
        }
    }
    
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        parent[y] = x;
        lca_id[x] = lca(lca_id[x], lca_id[y]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> M1 >> M2 >> Q;
    
    // 读入系统1
    sys1.n = N; sys1.m = M1;
    // ... 读入枢纽和边
    
    // 读入系统2  
    sys2.n = N; sys2.m = M2;
    // ... 读入枢纽和边
    
    // 构建系统2的LCA
    dfs_lca(1, 0);
    
    // 处理系统1枢纽
    vector<pair<int, int>> hubs1; // (y, id)
    // ... 收集系统1枢纽
    
    sort(hubs1.rbegin(), hubs1.rend()); // 按y降序
    
    // 处理查询
    vector<pair<int, int>> queries; // (A, id)
    // ... 读入查询
    
    vector<int> ans(Q);
    sort(queries.rbegin(), queries.rend()); // 按A降序
    
    DSU dsu(N);
    int ptr = 0;
    
    for (auto [A, qid] : queries) {
        while (ptr < hubs1.size() && hubs1[ptr].first > A) {
            // 添加枢纽 hubs1[ptr]
            int hub_id = hubs1[ptr].second;
            // 找到它连接的所有连通块，合并
            // ... 实现合并逻辑
            ptr++;
        }
        
        // 收集当前所有连通块的LCA
        set<int> comps;
        for (int i = 0; i < N; i++) {
            comps.insert(dsu.find(i));
        }
        
        // 找到这些LCA中y坐标最小的
        int min_y = 0;
        for (int comp : comps) {
            int lca_id = dsu.lca_id[comp];
            int y = /* 系统2中节点lca_id的y坐标 */;
            if (y < min_y) min_y = y;
        }
        
        ans[qid] = min_y;
    }
    
    for (int i = 0; i < Q; i++) {
        cout << ans[i] << "\n";
    }
    
    return 0;
}

算法标签

• 树结构：两个系统都是树，需要处理树的性质
• 图论/连通性：核心是维护连通块
• 数据结构：并查集、LCA预处理
• 离线处理：对查询排序处理
• 贪心：按y坐标顺序添加/删除节点

总结

本题的关键在于理解两个通信系统的互补作用，并通过维护连通块在系统2中的LCA来确定必须保留的枢纽。通过离线处理和对枢纽的排序，我们可以在 $O((N+M+Q)\log N)$ 时间内解决所有查询。

注意边界情况：当所有村庄已经通过系统1连通时，系统2可以不保留任何枢纽（$B=0$）。