官方题解（中文整理）

基于 Daniel Zhu 的官方题解整理。

子任务 1：直接模拟

记 \(nx[i]\) 表示奶牛 \(i\) 的最好朋友。

最朴素的做法是：每过一个晚上，就对每头奶牛单独模拟它会走到哪里。

对于某头奶牛 \(i\)：

• 如果 \(i\) 自己在开派对，那么终点已经确定
• 否则就令 \(i = nx[i]\)，继续向前找

一次查询中，每头奶牛最坏可能走 \(O(N)\) 步，因此总复杂度为 \(O(MN^2)\)。

子任务 2：把问题看成森林

上面的模拟有明显重复。

如果某头奶牛 \(i\) 和它的最好朋友 \(nx[i]\) 都没有开派对，那么它们最终会走向同一场派对，只不过 \(i\) 比 \(nx[i]\) 多走一步。

于是我们可以建立一张有向图：

• 对于所有没有开派对的奶牛 \(i\)，连一条 \(i \to nx[i]\) 的边
• 所有开派对的奶牛视为根

这样得到的结构是一片森林，每棵树的根就是一场派对。某场派对最终会吸引多少奶牛，等于对应那棵树的大小。

对每个晚上重新建图并做 DFS，就能求出所有根对应的子树大小。单次复杂度 \(O(N)\)，总复杂度 \(O(NM)\)。

正解：倒序处理 + 并查集

问题在于：若按正序处理，每次新增或修改一个派对，本质上可能让一棵树被“拆开”，而拆分在并查集中不好处理。

于是考虑倒序。

如果把操作顺序反过来，那么原问题中的“新增一个派对”就会变成“删除一个派对”。当一个派对被删除时，对应的那棵树不会被拆开，反而是这棵树的根接到它的最好朋友那里，与另一棵树合并。

合并是并查集最擅长维护的。

维护内容

对每个并查集连通块维护：

• 该块大小
• 该块最终会走到的根

此外还要记录每头奶牛在倒序过程中，当前是否仍有派对，以及派对的类型。

倒序过程

先把所有操作都读入，并把每头奶牛经历过的派对类型按时间存下来。

在“最终状态”下：

• 若一头奶牛当前没有派对，就把它和 \(nx[i]\) 合并
• 若它当前有派对，那么它就是一棵树的根

这样就能得到最后一天的答案。

之后倒序撤销每个操作：

• 如果这头奶牛撤销后仍然还有更早的派对类型，那么只是派对类型发生切换，块大小不变，只需从一个类型计数转移到另一个类型计数
• 如果撤销后它不再举办任何派对，那么这棵树会并入 \(nx[i]\) 所在的树，对应并查集合并

整个过程中，每次操作只涉及常数次并查集操作。

复杂度

总复杂度为 \(O(M \alpha(N))\)，其中 \(\alpha\) 为反阿克曼函数。