「COI 2025」Lirili Larila 题解

核心思路

1. 问题转化

我们有一个仙人掌图（每个节点最多属于一个环的连通图），需要选择两个起点 $u$ 和 $v$，使得：

• 距离 $u$ 更近的节点数为 $A$
• 距离 $v$ 更近的节点数为 $B$
• 距离相等的节点未被征服

2. 关键观察

Voronoi划分：节点归属由到两个起点的距离决定：

• 如果 $dist(u,x) < dist(v,x)$，则 $x$ 属于 $u$
• 如果 $dist(v,x) < dist(u,x)$，则 $x$ 属于 $v$
• 如果 $dist(u,x) = dist(v,x)$，则 $x$ 未被征服

3. 树的情况分析

对于树的情况，有一个重要性质：

• 如果选择两个节点 $u$ 和 $v$，那么 Voronoi 边界恰好是 $u-v$ 路径上的中点
• 归属关系可以通过 BFS 从两个起点计算

4. 仙人掌图特性

由于是仙人掌图（每个节点最多属于一个环），我们可以：

• 将图分解为环和树部分
• 利用环的对称性寻找合适的起点对
• 在环上，距离计算需要考虑两条路径

5. 算法框架

方法1：直径端点试探

1. 找到图的直径端点 $d_1$ 和 $d_2$
2. 在直径路径上尝试不同的起点对
3. 对于每对候选 $(u,v)$，计算归属节点数

方法2：随机化搜索

1. 随机选择候选起点对
2. 使用多源 BFS 计算归属
3. 验证是否满足 $A$ 和 $B$ 的要求

6. 优化策略

预处理：

• 预先计算所有节点对之间的距离（对于小数据）
• 使用多源 BFS 减少计算量

剪枝：

• 如果 $A + B > n$，无解（但题目保证有解）
• 优先尝试距离较远的点对

算法实现

复杂度分析

• 直径计算：$O(n + m)$
• 单次归属计算：$O(n + m)$
• 总复杂度：$O(k(n + m))$，其中 $k$ 是尝试的起点对数量

关键代码结构

// 计算从起点u和v开始的归属
pair<int, int> calculateOwnership(int u, int v) {
    vector<int> dist_u(n + 1, -1), dist_v(n + 1, -1);
    
    // 双源BFS
    auto multiSourceBFS = [&](const vector<int>& sources, vector<int>& dist) {
        queue<int> q;
        for (int s : sources) {
            dist[s] = 0;
            q.push(s);
        }
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int y : adj[x]) {
                if (dist[y] == -1) {
                    dist[y] = dist[x] + 1;
                    q.push(y);
                }
            }
        }
    };
    
    multiSourceBFS({u}, dist_u);
    multiSourceBFS({v}, dist_v);
    
    int cnt_u = 0, cnt_v = 0;
    for (int i = 1; i <= n; i++) {
        if (dist_u[i] < dist_v[i]) cnt_u++;
        else if (dist_v[i] < dist_u[i]) cnt_v++;
    }
    
    return {cnt_u, cnt_v};
}