C. 年度蚂蚁集会 详细题解

题目核心理解

一棵 $n$ 个节点的树上，每个节点初始有 $1$ 只蚂蚁。 你可以下达指令：让节点 $u$ 的蚂蚁移向相邻节点 $v$。 规则：蚂蚁只在 $v$ 的蚂蚁数 $\ge u$ 的蚂蚁数时移动。 可以无限次操作，问是否能把所有蚂蚁集中到同一个节点。

核心思路

1. 关键性质

• 非空节点始终构成一个连通块，只有当前连通块的叶子节点可以移动。
• 每次只能把蚂蚁从叶子移向内部，且必须满足叶子大小 $\le$ 父亲大小。
• 如果某一轮最小的叶子无法移入父亲，则所有更大的叶子更无法移动，直接无解。

2. 模拟规则

• 维护当前树的叶子节点（度数为 $1$ 的点）。
• 每次取出一个叶子 $u$，找到其唯一相邻的非空父亲 $p$。
• 若 $sz[u] > sz[p]$，则无法合并，输出 NO。
• 否则将 $sz[u]$ 合并到 $sz[p]$，删掉叶子 $u$，父亲度数减一。
• 重复直到只剩一个节点，输出 YES。

3. 最优性依据

只有从小到大合并叶子才能保证每一步都合法。 任何合法的最终集合点，一定可以通过这种叶子收缩方式得到。

算法流程

1. 读入树，建邻接表，初始化每个点大小 $sz[i]=1$，度数为实际度数。
2. 把所有初始叶子（度数 $=1$）加入队列。
3. 每次取出队首叶子 $u$，标记已删。
4. 找到 $u$ 未被删除的邻居 $p$（父亲）。
5. 若 $sz[u] > sz[p]$，输出 NO 并结束。
6. 否则 $sz[p] += sz[u]$，$p$ 度数减一；若度数变为 $1$ 则入队。
7. 直到只剩一个节点，输出 YES。

公式与复杂度分析

合并条件：

每次合并后：

复杂度

• 建图、初始化：$O(n)$
• BFS 收缩过程：每个点进出队列一次，$O(n)$
• 总时间复杂度：$O(n)$

可轻松处理 $n\le 2\times 10^5$ 的数据，在 $2$ 秒时限内稳定通过。