[DS记录]P5529 [Ynoi2012] 梦断 SCOI2017

**题意** ： 给出一棵 $n$ 个点的树，每个点有一个 $1\sim k$ 内的颜色。 定义同色块为保留同色边后的连通块。 支持下列操作 ： - 修改某个点的颜色。 - 修改点 $u$ 所在同色块的颜色。 - 查询点 $u$ 所在同色块的最深点与最浅点的深度差。 $n,m\leq 10^5,k\leq 30$ ，时限$\texttt{1s}$ ，空限$\texttt{125M}$。 ------------ 蒟蒻第一次写 ETT ，本题细节较多，讲得不好请见谅 qwq 称 $u$ 与父亲相连的边为“向上边”，称 $u$ 与直接儿子相连的边为“向下边”。 - ## 不考虑操作二 - ### ETT 与边连通块 将一条边的颜色定义为较深的端点的颜色，用 **ETT** 维护同色**边连通块**。 （ETT 维护的是括号序列，一对括号可以看做一条边的一进一出）  图中蓝框是一个“边连通块”的范围，而红框是一个题目中“同色块”的范围，注意其中的不同之处。 - ## findrt 考虑如何利用这个结构找出某个点所在的同色块的最浅点。 在每棵 ETT （代表一个边联通块）的根记下该边联通块的最浅点（如图黑点）。 对于点 $u$ ，只需要找出 $u$ 所在的 ETT 的根，然后找出边联通块最浅点 $v$ ，再查询 $u$ 到 $v$ 的路径上倒数第二个点即可得知答案。 - ## 查询 先找出 $u$ 的同色块的最浅点 $v$。 将 $v$ 的向上边的一对括号内部的东西 $\rm spilt$ 出来，这就是 $u$ 所在的同色块。 在 ETT 中维护子树最深点，容易回答询问。 - ## 单点修改 修改点 $v$ 的颜色，相当于修改边 $l=u\rightarrow v$ （ $u$ 浅 $v$ 深）的颜色。 记原来的颜色为 $c_0$ ，新的颜色为 $c_1$。（需要保证 $c_0\neq c_1$） 记 $son_{u,c}$ 表示 $u$ 的任意一个颜色为 $c$ 的儿子。 每次修改后只需要更新 $son_v$ ，用 `std::set` 维护，复杂度是 $O(\log)$ 的。空间也可以做到线性。 将边 $l$ 的两个括号从所在的 ETT 上删除，将原来的 ETT 分为三个部分 ：  考虑 $v$ 处新产生的连通性，找出 $son_{v,c_1}$ ，将其所在的 ETT 连接为 $l$ 的子树。（塞入 $l$ 的一对括号之中） 考虑 $u$ 处新产生的连通性，尝试找到 $t=son_{u,c_1}$ ，若存在，则将 $l$ 的 ETT 插入 $t$ 所在的 ETT 中 $t$ 右括号的右侧（表示并列）。 - ## 考虑操作二 - ## 对 $son$ 的修正 首先对 $son$ 稍作修正。若 $u$ 点的颜色为 $c$ ，钦定 $son_{u,c}$ 为未定义，否则操作二就会影响到大量 $son$ 的取值。 观察我们实际上用到 $son$ 的场合。 将 $u\rightarrow v$ 的颜色从 $c_0$ 改为 $c_1$ 时 ： - 考虑 $v$ 处新产生的连通性，找出 $son_{v,c_1}$ …… 此时 $v$ 的颜色是 $c_0\neq c_1$ ，无影响。 - 考虑 $u$ 处新产生的连通性，尝试找到 $t=son_{u,c_1}$ …… 此时 $u$ 的颜色可能是 $c_1$ ，但此时直接令 $t=u$ 即可处理。 这又需要支持查询某点的颜色，类似上文对边联通块最浅点的处理，直接记在 ETT 的根上。 - ## 同色块修改 首先将需要修改的同色块 $\rm spilt$ 出来，设颜色被改为 $c$。 记同色块的最浅点为 $v$ ，$v$ 的父亲为 $u$ 。 考虑 $u$ 处新增的连通性，这个和单点类似，不再赘述。 除了 $u$ ，也会有其他地方产生新的连通性。我们需要找出连通块中所有 存在颜色为 $c$ 的向下边的点。 对于一个这样的点 $v$ ，找出 $son_{v,c}$ （$v$ 原来的颜色必不是 $c$），将其所在的 ETT 连接为 $v$ 的子树。 在 ETT 中用 `uint` 状压“子树内是否存在拥有颜色 $1\sim k$ 的向下边的点” ，然后大力搜索，即可快速找到所有的 $v$。 记 $c_u$ 为 {$u$ **和**直接儿子} 中的不同颜色数。我们发现，找出的 $v$ 都满足 $c_v\geq 2$ ，而且操作后 $c_v$ 至少减少 $1$。 $c$ 的初始和为 $O(n)$ ，而每次单点修改只会增大 $O(1)$ ，故复杂度均摊正确。 总时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。 ```cpp ```