「POI2014 R3」蚁巢 Ant colony 题解

问题分析

我们有一棵树表示蚁巢结构，叶子节点（度数为1的节点）是入口。每个入口有 $g$ 群蚂蚁，规模分别为 $m_1, m_2, \ldots, m_g$。蚂蚁在节点处按度数分裂，食蚁兽在指定通道上吞噬恰好 $k$ 只蚂蚁的群体。

关键观察：蚂蚁分裂过程是可逆的！我们可以从食蚁兽位置反向推导出能到达这里的蚂蚁初始规模范围。

数学模型

设食蚁兽在边 $(u,v)$ 上。对于从某个入口到达食蚁兽的路径，蚂蚁会经过一系列分裂：

• 在度数为 $d$ 的节点，蚂蚁群分裂为 $d$ 组（如果是入口节点，实际可走通道数为 $d-1$，因为来的那条通道不算）
• 要使得在食蚁兽位置有恰好 $k$ 只蚂蚁，初始规模必须满足特定条件

分裂规则形式化

设路径为：入口 $l$ → 节点 $p_1$ → $p_2$ → ... → 食蚁兽位置

在路径上的每个节点 $p_i$（除了最后一个），如果它的度数为 $deg_i$，那么：

• 如果 $p_i$ 是入口：分裂为 $deg_i - 1$ 组（因为有一条通道是进来的）
• 如果 $p_i$ 不是入口：分裂为 $deg_i - 1$ 组（有一条通道是进来的）
• 最后一个节点（食蚁兽所在边的一端）：不分裂

因此，从入口 $l$ 到食蚁兽，蚂蚁群总共分裂的次数和分裂因子是可以计算的。

解决方案

算法思路

1. 建树并确定入口：度数为1的节点是入口
2. 确定食蚁兽边：输入的第一条边
3. DFS计算分裂乘积：从食蚁兽边的两端分别DFS，计算到每个入口的分裂乘积
4. 计算有效范围：对于每个入口，计算能产生恰好 $k$ 只蚂蚁的初始规模范围
5. 统计答案：对每个入口的蚂蚁群，统计在有效范围内的数量

详细算法

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

typedef long long ll;
const int MAXN = 1e6 + 5;

vector<int> G[MAXN];
int deg[MAXN];
int n, g, k;
vector<int> m;
int entrance[MAXN], entrance_cnt;
ll ans = 0;

// 食蚁兽边的两个端点
int u0, v0;

// 从节点u开始DFS，计算到每个入口的分裂乘积
// parent: 父节点，prod: 当前累积的分裂乘积，dir: 方向标记
void dfs(int u, int parent, ll prod, int dir) {
    if (prod > 1e18) return; // 防止溢出
    
    // 如果当前节点是入口（度数为1且不是食蚁兽边的特殊情况）
    if (deg[u] == 1 && u != u0 && u != v0) {
        // 计算能产生恰好k只蚂蚁的初始规模范围
        // 初始规模 * 1/prod = k  => 初始规模 = k * prod
        // 但由于整数除法，实际范围是 [k*prod, (k+1)*prod - 1]
        ll lower_bound = (ll)k * prod;
        ll upper_bound = (ll)(k + 1) * prod - 1;
        
        if (lower_bound > 1e9) return; // 超出蚂蚁群规模上限
        
        // 在当前入口的蚂蚁群中统计在范围内的数量
        for (int i = 0; i < g; i++) {
            if (m[i] >= lower_bound && m[i] <= upper_bound) {
                ans++;
            }
        }
        return;
    }
    
    // 计算分裂因子：度数为d的节点，分裂为d-1组（减去来的那条边）
    // 但如果是起始节点（食蚁兽边的端点），分裂因子就是度数（没有来的边）
    int split_factor;
    if (parent == -1) {
        // 起始节点
        split_factor = deg[u];
    } else {
        // 中间节点
        split_factor = deg[u] - 1;
    }
    
    for (int v : G[u]) {
        if (v == parent) continue;
        // 注意：乘积是乘以上分裂因子，因为初始规模要乘以split_factor才能得到上一层的规模
        dfs(v, u, prod * split_factor, dir);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> g >> k;
    m.resize(g);
    for (int i = 0; i < g; i++) {
        cin >> m[i];
    }
    
    // 读入第一条边（食蚁兽所在边）
    cin >> u0 >> v0;
    G[u0].push_back(v0);
    G[v0].push_back(u0);
    deg[u0]++; deg[v0]++;
    
    // 读入其他边
    for (int i = 1; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
        deg[a]++; deg[b]++;
    }
    
    // 对食蚁兽边的两个端点分别进行DFS
    // 从u0向v0方向搜索（不包括v0本身）
    for (int v : G[u0]) {
        if (v == v0) continue;
        dfs(v, u0, deg[u0], 0); // 起始分裂因子是u0的度数
    }
    
    // 从v0向u0方向搜索（不包括u0本身）  
    for (int v : G[v0]) {
        if (v == u0) continue;
        dfs(v, v0, deg[v0], 1); // 起始分裂因子是v0的度数
    }
    
    cout << ans << endl;
    
    return 0;
}

关键点解释

分裂乘积的计算

从食蚁兽位置反向推导：

• 如果在节点处蚂蚁分裂为 $d$ 组，那么要得到 $k$ 只蚂蚁，上一层的规模必须是 $k \times d$
• 因此从入口到食蚁兽，初始规模 = $k \times d_1 \times d_2 \times \cdots \times d_t$

范围计算

由于蚂蚁群规模是整数，实际范围是：

• 下界：$k \times prod$
• 上界：$(k + 1) \times prod - 1$

特殊情况处理

1. 起始节点：食蚁兽边的端点，分裂因子是节点的度数（没有"来的边"要减去）
2. 中间节点：分裂因子是度数减1（减去来的那条边）
3. 入口节点：在DFS中自动处理为叶子节点

复杂度分析

• 建树：$O(n)$
• DFS遍历：$O(n)$
• 统计答案：$O(g \times \text{入口数量})$，最坏 $O(n \times g)$，但实际入口数量很少

由于 $n, g \leq 10^6$，如果入口数量很多，可能需要优化统计过程（如对蚂蚁群规模排序后二分查找）。

优化版本

// 优化：对蚂蚁群排序，使用二分查找统计范围内的数量
sort(m.begin(), m.end());

void dfs_optimized(int u, int parent, ll prod, int dir) {
    if (prod > 1e18) return;
    
    if (deg[u] == 1 && u != u0 && u != v0) {
        ll lower_bound = (ll)k * prod;
        ll upper_bound = (ll)(k + 1) * prod - 1;
        
        if (lower_bound > 1e9) return;
        
        // 二分查找统计范围内的数量
        auto it_l = lower_bound(m.begin(), m.end(), lower_bound);
        auto it_r = upper_bound(m.begin(), m.end(), upper_bound);
        ans += (it_r - it_l);
        return;
    }
    
    int split_factor = (parent == -1) ? deg[u] : deg[u] - 1;
    for (int v : G[u]) {
        if (v == parent) continue;
        dfs_optimized(v, u, prod * split_factor, dir);
    }
}

这样优化后，统计答案的复杂度为 $O(\text{入口数量} \times \log g)$，总体复杂度 $O(n + \text{入口数量} \times \log g)$。