小圆抱抱 |【解题报告】P9867 [POI 2021/2022 R2] kon

Starrykiller · 2025-04-23 11:38:11 · 题解

参考官方题解。

定义邻域：点 u 的邻域 N(u)=\{v: (u,v)\in E\}，即 u 出边连向点的集合。

### Subtask 2 > **Lemma.** > > 如果只有 $\texttt{Z}$ 操作，在任意时刻，图的形态都是完全二分图。 > > **Proof.** 初始时显然，归纳即可证明。$\square

直接维护二分图两部的点数，以及每个点属于哪一部即可。时间复杂度 \Theta(q)。结合 Subtask 1 期望得分 30。

Lemma.

在任意时刻，图的形态都是二分图。

Proof. 初始时显然，归纳即可证明。\square

Subtask 1 的解法实在是太不牛了，究其原因是我们没有挖掘题目的性质，每次暴力地复制。

感性理解一下，发现有很多点的邻域都有公共的元素。考虑优化这个过程。

设二分图左部点集为 L，右部点集为 R。

不失一般性地假设我们在维护 L 的邻域。考虑一棵树，我们用一条边代表一个右部点，一条路径 \operatorname{path}(i)=(\operatorname{st}(i),\operatorname{ed}(i)) 代表左部点 i 的邻域。

依次考虑四种操作：

- 设 $l$ 的链底为 $\operatorname{ed}(l)$，新加的右部点为 $r$。加一条代表右部点的边 $(\operatorname{ed}(l),r)$，更新链底 $\operatorname{ed}(l)\gets r$。
- 设新加的左部点为 $l$。找到 $r$ 对应的连边，更新 $\operatorname{path}(i)$ 即可。
- 设新加的左部点为 $l'$，直接令 $\operatorname{path}(l')\gets \operatorname{path}(l)$（复制）即可。
- 设新加的右部点为 $r'$。我们要对任意包含 $r$ 这条边的路径，都加入一条代表 $r'$ 的边。 - 考虑将 $r$ 对应的边拆成两条，一条对应 $r$ 一条对应 $r'$ 即可。

不难注意到，每个 \operatorname{path} 都是某个点向上跳若干步得到的一条链。

使用树上差分，我们就直接做到了 \Theta(q)（对于拆边操作，可以使用懒标记维护）。结合 Subtask 1&2 期望得分 65。

经典套路：离线操作，获得最终树的形态。给每条边权赋 0/1，表示当前时刻这条边是否存在。

这是一个经典问题（根链加/单点查），使用 DFS 序+树状数组可以简单地 \Theta(q\log q)。期望得分 100。