「联合省选 2020 B」消息传递 题解

问题分析

这个问题要求计算在树形社交网络中，从某个源点 $x$ 开始传播消息，第 $k$ 天时新收到消息的人数。

关键约束

• 树形结构：$n$ 个节点，$n-1$ 条边
• 多组测试数据：$T \leq 5$
• 大规模数据：$n, m \leq 10^5$
• 查询：对于每个 $(x, k)$，求距离 $x$ 恰好为 $k$ 的节点数

算法思路

核心算法：点分治

代码使用了点分治（重心分解）算法来解决树上距离查询问题。

点分治原理

1. 找重心：在子树中找到重心，将树分割为平衡的子树
2. 处理经过重心的路径：计算所有经过当前重心的路径对查询的贡献
3. 递归处理：对分割后的子树递归处理

算法步骤

1. 重心分解

void fincen(int u, int fa = 0, int mx = 0) {
    siz[u] = 1;
    for (int v : adj[u])
        if (v != fa && !del[v])
            fincen(v, u), siz[u] += siz[v], cmax(mx, siz[v]);
    cmax(mx, all - siz[u]), mx <= (all >> 1) ? cen[cen[0] != 0] = u, 1 : 0;
}

2. 处理查询

对于每个重心 $u$：

• 统计距离：维护 tot[d] 数组，记录距离重心为 $d$ 的节点数
• 计算贡献：对于每个查询 $(x, k)$，如果 $x$ 到重心的距离为 $dep[x]$，且 $k \geq dep[x]$，则贡献为 $tot[k - dep[x]]$

void get(int u, int fa) {
    dep[u] = dep[fa] + 1;
    for (pii q : vec[u])
        if (q.fi >= dep[u])
            ans[q.se] += tot[q.fi - dep[u]];
    // ...
}

3. 容斥处理

为了避免重复计算，对每个重心的子树进行两次遍历：

• 第一次：计算当前子树的贡献
• 第二次：反向遍历，确保不重复计算

复杂度分析

• 预处理：$O(n \log n)$ 构建点分树
• 单次查询：$O(\log n)$ 在点分树中处理
• 总复杂度：$O((n + m) \log n)$，适合 $n, m \leq 10^5$

代码关键部分解析

数据结构

vector<int> adj[MAXN + 3];    // 邻接表存储树
vector<pii> vec[MAXN + 3];    // vec[x] = {(k, query_id)} 存储每个节点的查询
int tot[MAXN + 3];            // tot[d]: 距离当前重心为d的节点数
bool del[MAXN + 3];           // 标记已删除的重心

主算法流程

void sol(int u) {
    // 1. 找重心
    all = siz[u], cen[0] = cen[1] = 0, fincen(u), u = cen[0];
    
    // 2. 标记重心并初始化
    tot[dep[u] = 0]++, del[u] = 1;
    
    // 3. 处理所有子树
    for (int v : adj[u])
        if (!del[v])
            get(v, u), ins(v, u);  // 统计贡献并插入
    
    // 4. 处理重心自身的查询
    for (pii q : vec[u])
        if (q.fi >= dep[u])
            ans[q.se] += tot[q.fi - dep[u]];
    
    // 5. 清空并反向处理（容斥）
    clr(u), reverse(adj[u].begin(), adj[u].end());
    // ... 重复步骤3
    
    // 6. 递归处理子树
    for (int v : adj[u])
        if (!del[v])
            sol(v);
}

算法标签

🏷️ 主要算法

点分治 - 利用重心分解处理树上路径问题 分治算法 - 将问题分解为子问题递归解决

🏷️ 数据结构

树结构 - 社交网络的天然表示 数组计数 - 使用 tot 数组统计距离分布

🏷️ 优化技术

重心分解 - 保证树的分割平衡 容斥原理 - 避免重复计数 离线处理 - 预先存储查询，批量处理

🏷️ 问题类型

树上距离查询 - 查询特定距离的节点数量 路径统计 - 统计满足距离条件的路径端点

🏷️ 复杂度类别

对数线性 - $O(n \log n)$ 处理大规模数据

这个解决方案通过点分治算法高效地处理了树上距离查询问题，利用重心的性质将问题分解，通过容斥避免重复计算，在 $O(n \log n)$ 时间内解决了大规模数据的查询问题。