「雅礼集训 2018 Day10」文明 题解

问题重述

给定一棵 $n$ 个节点的树，进行 $q$ 次游戏。每次游戏有 $k$ 个玩家，初始位置分别为 $a_1, a_2, \dots, a_k$（黈力是 $1$ 号玩家，初始位置为 $a_1$）。玩家轮流操作，每轮操作将自己的领土向外扩展 $1$ 的距离（占领所有相邻的未占领节点）。问黈力最终能占领多少个节点。

问题转化

通过分析游戏过程，可以得出以下关键性质：

1. 扩展速度：所有玩家每轮都以相同速度（距离 $1$）扩展

2. 竞争规则：节点 $v$ 最终被玩家 $i$ 占领当且仅当：

   • $d(v, a_i) = \min_{j} d(v, a_j)$（距离最小）
   • 在距离相同的玩家中，编号最小的获胜（黈力是 $1$ 号，有优先级）

3. 最终状态：每个节点属于离它最近的初始点，距离相同时属于编号最小的玩家

因此，问题转化为：在树上为每个节点分配离它最近的"首都" $a_i$，距离相同时选择编号小的，统计黈力（$a_1$）占领的节点数。

算法思路

核心观察

设黈力的初始点为 $rt$（代码中的变量名），其他玩家的初始点为 $vex$。对于任意节点 $v$：

1. 如果 $v$ 到 $rt$ 的距离 $\leq$ 到其他所有 $vex$ 中点的距离，则 $v$ 属于黈力
2. 否则属于其他玩家

这等价于：黈力占领的区域是以 $rt$ 为中心的"Voronoi 区域"，边界由到 $rt$ 和到其他点距离相等的点构成。

关键引理

对于两个点 $u$ 和 $v$，它们的势力范围分界点 $mid(u,v)$ 定义为：

• 如果 $d(rt,u) = d(rt,v)$，则分界点在连接路径的中点
• 更一般地，$mid(u,v)$ 是使得 $d(rt,x) = d(u,x)$ 的点 $x$

重要性质：$mid(u,v)$ 到 $rt$ 和 $u$ 的距离差为 $d(rt,u)/2$（取整处理）。

算法步骤

1. 预处理

• 使用树链剖分或倍增法预处理 LCA，支持 $O(\log n)$ 查询任意两点距离
• 计算每个节点的 DFS 序、子树大小、重链等信息

2. 对于每次查询

• 输入 $k$ 个点，$rt = a_1$ 是黈力的首都
• 对于每个其他玩家的点 $u$：
  • 计算 $mid = Find(u)$：$rt$ 和 $u$ 的势力分界点
  • 在 DFS 序中标记 $mid$ 的子树（这些节点离 $u$ 更近）

3. 势力范围计算

设 $S$ 为所有分界点的 DFS 序集合（包括 $rt$ 自身）。

情况 1：没有祖先关系的点

• 按 DFS 序排序，贪心计算被其他玩家占领的子树
• 如果某个分界点的子树完全在当前已覆盖区间外，则整个子树被其他玩家占领
• 从答案 $n$ 中减去这些子树的大小

情况 2：存在分界点是 $rt$ 的祖先

• 设 $ances$ 是 $rt$ 的最近祖先分界点
• $ances$ 的子树中，只有深度 $> dep[ances]$ 的部分可能属于黈力
• 需要特殊处理 $ances$ 的父节点方向的部分

核心函数解析

Find(u) 函数

计算 $rt$ 和 $u$ 的势力分界点：

inline int Find(int u) {
    int lca = LCA(rt, u);
    int dist = dep[u] + dep[rt] - 2 * dep[lca];
    int k = (dist - 1) / 2;  // 距离除以2下取整
    
    if (k <= dep[u] - dep[lca])
        return Anc(u, k);    // 在u到lca的路径上
    else
        return Anc(rt, dist - k);  // 在rt到lca的路径上
}

势力范围计算逻辑

1. 收集所有分界点：对于每个其他玩家点 $u$，计算 $Find(u)$ 并加入集合
2. 按 DFS 序处理：
   • 如果分界点 $p$ 的 DFS 序区间 $[dfn[p], dfn[p]+siz[p]-1]$ 与已覆盖区间不重叠
   • 则该整个子树被其他玩家占领
3. 处理祖先关系：
   • 如果存在分界点是 $rt$ 的祖先
   • 需要减去 $ances$ 的父节点方向的节点（这些节点离祖先更近）

时间复杂度分析

• 预处理：$O(n \log n)$
• 每次查询：
  • 计算 $k-1$ 个分界点：$O(k \log n)$
  • 集合操作：$O(k \log k)$
  • 总复杂度：$O(k \log n)$
• 总复杂度：$O(n \log n + \sum k_i \log n) \leq O(n \log n + 10^6 \log n)$，可以通过

代码实现要点

1. 树链剖分：用于快速求 LCA 和树上距离
2. 倍增法：Anc(u, x) 函数用于求 $u$ 的 $x$ 级祖先
3. DFS 序性质：子树在 DFS 序中是连续区间
4. 集合维护：使用 std::set 维护分界点的 DFS 序

正确性证明

关键引理证明

对于任意节点 $v$：

• 如果 $v$ 在 $mid(u,rt)$ 的子树中且不在更近的其他分界点子树中，则 $d(v,rt) > d(v,u)$
• 因此 $v$ 被玩家 $u$ 占领
• 反之，如果 $v$ 不在任何分界点的子树中，则 $d(v,rt) \leq d(v,u_i)$ 对所有 $u_i$ 成立

贪心正确性

按 DFS 序处理时，由于子树区间是连续的，且区间要么包含要么不相交，可以使用贪心选择：

• 如果当前区间起点大于已覆盖区间的终点，说明这是一个新的不相交子树
• 该子树全部被其他玩家占领

样例验证

以题目样例第一组数据为例：

• $n=6$，$k=2$，$rt=1$，$u=3$
• 计算 $Find(3)$：$dist(1,3)=1$，$k=0$，返回 $3$
• 分界点集合：$\{1,3\}$
• $3$ 的子树大小为 $3$（节点 $3,5,6$）
• 但这些节点中，$3$ 离 $3$ 更近，$5,6$ 离 $3$ 比离 $1$ 更近
• 黈力占领节点：$1,2,4$，共 $3$ 个

总结

本题通过将游戏过程转化为树上最近邻分类问题，利用树链剖分和 DFS 序的性质，高效计算黈力的势力范围。核心在于理解势力分界点的计算和处理祖先关系的特殊情况。算法时间复杂度优秀，能够处理 $n,q \leq 5\times 10^5$，$\sum k_i \leq 10^6$ 的大规模数据。