「KTSC 2024 R2」病毒 题解

问题分析

我们需要模拟病毒在树形城市网络中的传播过程。关键挑战在于：

• 树结构上的距离计算
• 每个人有特定的活动范围限制
• 病毒通过传播媒介（地点）在人与人之间传播
• 需要高效处理 $N, M \leq 10^5$ 的大规模数据

算法思路：点分治 + 双堆优化

核心思想

利用点分治（重心分解）来高效处理树上的距离查询，结合双优先队列来模拟病毒传播过程。

1. 点分治预处理

重心分解构建

int dfs(int v, int p = -1) {
    sz[v] = 1;
    for (auto u : adj[v]) {
        if (vis[u] or u == p) continue;
        sz[v] += dfs(u, v);
    }
    return sz[v];
}

int find(int v, int tot, int p = -1) {
    for (auto u : adj[v]) {
        if (u == p or vis[u]) continue;
        if (sz[u] * 2 > tot) return find(u, tot, v);
    }
    return v;
}

void centroid(int v) {
    v = find(v, dfs(v));  // 找到重心
    dfs1(v, v);           // 从重心开始DFS
    vis[v] = true;
    for (auto u : adj[v]) {
        if (vis[u]) continue;
        centroid(u);      // 递归处理子树
    }
}

作用：将树分解为多个重心，每个节点记录到各个重心的距离。

距离信息记录

void dfs1(int v, int pp, int p = -1, int d = 0) {
    pari[v].push_back({pp, d});  // 节点v到重心pp的距离为d
    v1[pp].push_back({d, v});    // 重心pp的覆盖节点列表
    
    for (auto u : adj[v]) {
        if (u == p or vis[u]) continue;
        dfs1(u, pp, v, d + 1);
    }
}

2. 数据结构初始化

居民可达范围处理

for (int i = 0; i < m; i++) {
    int id = P[i];
    for (auto p : pari[id]) {
        par[i].push_back(p);
        if (D[i] >= p.s)
            v2[p.f].push_back({D[i] - p.s, i});  // 记录居民在重心下的可达范围
    }
}

排序优化

for (int i = 0; i < n; i++) {
    sort(v1[i].rbegin(), v1[i].rend());  // 按距离降序排序
    sort(v2[i].begin(), v2[i].end());    // 按剩余距离升序排序
}

3. 病毒传播模拟

双优先队列设计

priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;  // 居民感染时间队列
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pqi; // 地点传播队列

d[0] = 0;  // 第0个人在时间0感染
pq.push({0, 0});

传播逻辑核心

居民感染触发地点传播：

auto upd1 = [&](int v) {
    for (auto p : par[v]) {  // 遍历该居民相关的所有重心
        if (D[v] < p.s) continue;
        int r = D[v] - p.s;  // 在重心p.f下的剩余可达距离
        
        while (!v1[p.f].empty() and v1[p.f].back().f <= r) {
            int id = v1[p.f].back().s;  // 可达的地点
            v1[p.f].pop_back();
            if (did[id]) continue;
            did[id] = true;
            pqi.push({C[id] + d[v], id});  // 地点在d[v]+C[id]时间开始传播
        }
    }
};

地点传播触发居民感染：

auto upd2 = [&](int v, ll dis) {
    for (auto p : pari[v]) {  // 遍历地点v相关的所有重心
        int r = p.s;  // 地点v到重心p.f的距离
        
        while (!v2[p.f].empty() and v2[p.f].back().f >= r) {
            int id = v2[p.f].back().s;  // 可达的居民
            v2[p.f].pop_back();
            if (dis < d[id]) {
                d[id] = dis;  // 更新居民感染时间
                pq.push({d[id], id});
            }
        }
    }
};

4. 主传播循环

while (!pq.empty() or !pqi.empty()) {
    if (pqi.empty() or (!pq.empty() and pq.top().f < pqi.top().f)) {
        // 处理居民感染：触发地点传播
        auto v = pq.top(); pq.pop();
        if (d[v.s] != v.f) continue;
        upd1(v.s);  // 感染者触发新的地点传播
    } else {
        // 处理地点传播：触发居民感染  
        auto v = pqi.top(); pqi.pop();
        upd2(v.s, v.f);  // 传播地点触发新的感染者
    }
}

算法复杂度分析

• 点分治预处理：$O(N \log N)$
• 排序操作：$O(N \log N)$
• 传播模拟：每个节点和居民最多被处理一次，$O((N+M) \log N)$
• 总复杂度：$O((N+M) \log N)$，满足大规模数据要求

关键优化技术

$1.$ 点分治：将树上距离查询转化为多个重心的局部查询

$2.$ 双队列模拟：分别处理居民感染和地点传播事件

$3.$ 贪心处理：按时间顺序处理事件，确保最早感染时间

$4.$ 懒删除：通过排序和弹出实现高效的范围查询

算法正确性

传播模型实现

• 传播媒介：通过点分治高效找到满足距离约束的传播地点
• 最早感染时间：使用优先队列确保按时间顺序处理
• 传播链：正确模拟病毒通过地点在人与人之间的传播

边界情况处理

• 不可达居民：感染时间保持 $\infty$，最终返回 $-1$
• 重复感染：通过距离比较确保记录最早感染时间
• 活动范围限制：通过距离约束正确建模

该解法通过点分治分解和事件驱动模拟，高效解决了树形网络上的病毒传播问题。